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

    <tr>
        <th>Summary</th>
        <td>
            [EarlyCSE] Assertion `!FoundVal && "Key already in new map?"' failed.
        </td>
    </tr>

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

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

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

<pre>
    Reproducer:
```
; bin/opt -passes=early-cse reduced.ll -S

define i32 @func_207(i16 %p_208.coerce, i32 %conv, i32 %0, i64 %1, ptr %p) {
entry:
  %conv1 = zext i16 %p_208.coerce to i32
  %conv31 = sext i32 %conv to i64
  %cmp.i = icmp eq i64 %conv31, 0
  %xor = xor i32 %conv, 1
  store i32 %xor, ptr %p, align 4
  %cmp2.i = icmp samesign ugt i32 %conv1, 31
  %shr.i601 = select i1 %cmp2.i, i32 0, i32 %conv1
  %cond.i602 = ashr i32 1, %shr.i601
 %conv6.i603 = trunc i32 %cond.i602 to i16
  %conv245 = trunc i16 %p_208.coerce to i8
  %mul.i628 = mul i8 -107, %conv245
  %conv247 = sext i8 %mul.i628 to i64
  %cond.i629 = call i64 @llvm.smin.i64(i64 0, i64 %conv247)
  %cmp249 = icmp slt i64 %cond.i629, 0
  %conv251 = zext i1 %cmp249 to i64
  %cmp1.i630 = icmp ugt i32 %conv1, 31
  %narrow.i631 = select i1 %cmp1.i630, i32 0, i32 %conv1
  %shr.i632 = zext i32 %narrow.i631 to i64
  %cond.i633 = lshr i64 %conv251, %shr.i632
  %cmp258 = icmp slt i16 %p_208.coerce, 0
  %2 = zext i1 %cmp258 to i16
  %cmp261 = icmp ugt i16 1, %2
  %conv263 = zext i1 %cmp261 to i64
  %cmp344 = icmp eq i16 %p_208.coerce, 0
  %conv345 = zext i1 %cmp344 to i32
  store i32 %conv345, ptr %p, align 4
  %conv351 = sext i32 %0 to i64
  %sub.i641 = call i64 @llvm.ucmp.i64.i64(i64 0, i64 %conv351)
  %conv353 = trunc i64 %sub.i641 to i16
  %3 = mul i16 %conv353, -1
  %conv355 = zext i16 %3 to i64
  %cmp356 = icmp sle i64 1, %conv355
  %conv357 = zext i1 %cmp356 to i32
  %conv359 = trunc i32 %conv357 to i8
  %conv.i650 = sext i8 %conv359 to i32
  %4 = icmp ugt i32 %conv, 0
  %shr.i652 = lshr i32 1, %conv
  %cmp9.i = icmp slt i32 %shr.i652, 1
  %or.cond.i = select i1 %4, i1 false, i1 %cmp9.i
  %shl.i653 = shl i32 %conv.i650, 1
  %5 = trunc i32 %shl.i653 to i8
  %cond.i654 = select i1 %or.cond.i, i8 0, i8 %5
  %conv3612 = sext i8 %cond.i654 to i32
 %conv3623 = trunc i64 %1 to i32
  %6 = or i32 1, %conv3612
  %or.cond.i655 = icmp slt i32 %6, 0
  %cmp3.i = icmp sgt i32 %conv3623, 0
  %or.cond4.i = or i1 %cmp3.i, %or.cond.i655
  %shr.i656 = select i1 %or.cond4.i, i32 0, i32 1
  %cond.i657 = ashr i32 %conv, %shr.i656
  %cmp.i658 = icmp slt i32 %cond.i657, 0
  %shr.i660 = select i1 %cmp.i658, i32 0, i32 1
  %cond.i661 = ashr i32 1, %shr.i660
  %conv365 = trunc i32 %cond.i661 to i16
 %add.i662 = or i16 1, %conv365
  %conv368 = sext i16 %add.i662 to i32
  ret i32 %conv368
}
```
```
opt: /data/zyw/llvm-project/llvm/include/llvm/ADT/DenseMap.h:419: void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::moveFromOldBuckets(BucketT*, BucketT*) [with DerivedT = llvm::DenseMap<{anonymous}::SimpleValue, llvm::ScopedHashTableVal<{anonymous}::SimpleValue, llvm::Value*>*, llvm::DenseMapInfo<{anonymous}::SimpleValue>, llvm::detail::DenseMapPair<{anonymous}::SimpleValue, llvm::ScopedHashTableVal<{anonymous}::SimpleValue, llvm::Value*>*> >; KeyT = {anonymous}::SimpleValue; ValueT = llvm::ScopedHashTableVal<{anonymous}::SimpleValue, llvm::Value*>*; KeyInfoT = llvm::DenseMapInfo<{anonymous}::SimpleValue>; BucketT = llvm::detail::DenseMapPair<{anonymous}::SimpleValue, llvm::ScopedHashTableVal<{anonymous}::SimpleValue, llvm::Value*>*>]: Assertion `!FoundVal && "Key already in new map?"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /data/zyw/llvm-build/bin/opt -passes=early-cse reduced.ll
1.      Running pass "function(early-cse<>)" on module "reduced.ll"
2.      Running pass "early-cse<>" on function "func_207"
 #0 0x00007ffff7def832 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/data/zyw/llvm-build/bin/../lib/libLLVMSupport.so.20.0git+0x1ef832)
 #1 0x00007ffff7dec9ef llvm::sys::RunSignalHandlers() (/data/zyw/llvm-build/bin/../lib/libLLVMSupport.so.20.0git+0x1ec9ef)
 #2 0x00007ffff7decb35 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007ffff7842520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #4 0x00007ffff78969fc pthread_kill (/lib/x86_64-linux-gnu/libc.so.6+0x969fc)
 #5 0x00007ffff7842476 gsignal (/lib/x86_64-linux-gnu/libc.so.6+0x42476)
 #6 0x00007ffff78287f3 abort (/lib/x86_64-linux-gnu/libc.so.6+0x287f3)
 #7 0x00007ffff782871b (/lib/x86_64-linux-gnu/libc.so.6+0x2871b)
 #8 0x00007ffff7839e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
 #9 0x00007ffff4efa75e llvm::DenseMap<(anonymous namespace)::SimpleValue, llvm::ScopedHashTableVal<(anonymous namespace)::SimpleValue, llvm::Value*>*, llvm::DenseMapInfo<(anonymous namespace)::SimpleValue, void>, llvm::detail::DenseMapPair<(anonymous namespace)::SimpleValue, llvm::ScopedHashTableVal<(anonymous namespace)::SimpleValue, llvm::Value*>*>>::grow(unsigned int) EarlyCSE.cpp:0:0
#10 0x00007ffff4efbd5a llvm::ScopedHashTable<(anonymous namespace)::SimpleValue, llvm::Value*, llvm::DenseMapInfo<(anonymous namespace)::SimpleValue, void>, llvm::RecyclingAllocator<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>, llvm::ScopedHashTableVal<(anonymous namespace)::SimpleValue, llvm::Value*>, 32ul, 8ul>>::insertIntoScope(llvm::ScopedHashTableScope<(anonymous namespace)::SimpleValue, llvm::Value*, llvm::DenseMapInfo<(anonymous namespace)::SimpleValue, void>, llvm::RecyclingAllocator<llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul, 128ul>, llvm::ScopedHashTableVal<(anonymous namespace)::SimpleValue, llvm::Value*>, 32ul, 8ul>>*, (anonymous namespace)::SimpleValue const&, llvm::Value* const&) EarlyCSE.cpp:0:0
#11 0x00007ffff4efdf19 (anonymous namespace)::EarlyCSE::processNode(llvm::DomTreeNodeBase<llvm::BasicBlock>*) (.isra.0) EarlyCSE.cpp:0:0
#12 0x00007ffff4efeef5 (anonymous namespace)::EarlyCSE::run() EarlyCSE.cpp:0:0
#13 0x00007ffff4f00796 llvm::EarlyCSEPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMScalarOpts.so.20.0git+0x100796)
#14 0x00007ffff6684345 llvm::detail::PassModel<llvm::Function, llvm::EarlyCSEPass, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMPasses.so.20.0git+0x84345)
#15 0x00007ffff38ee63d llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMCore.so.20.0git+0x2ee63d)
#16 0x00007ffff70a9445 llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMX86CodeGen.so.20.0git+0xa9445)
#17 0x00007ffff38ec628 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMCore.so.20.0git+0x2ec628)
#18 0x00007ffff70a9e05 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMX86CodeGen.so.20.0git+0xa9e05)
#19 0x00007ffff38ed28d llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/data/zyw/llvm-build/bin/../lib/../lib/libLLVMCore.so.20.0git+0x2ed28d)
#20 0x00007ffff7f9b1eb 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) (/data/zyw/llvm-build/bin/../lib/libLLVMOptDriver.so.20.0git+0x241eb)
#21 0x00007ffff7fa5619 optMain (/data/zyw/llvm-build/bin/../lib/libLLVMOptDriver.so.20.0git+0x2e619)
#22 0x00007ffff7829d90 (/lib/x86_64-linux-gnu/libc.so.6+0x29d90)
#23 0x00007ffff7829e40 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e40)
#24 0x0000555555555095 _start (/data/zyw/llvm-build/bin/opt+0x1095)
Aborted (core dumped)
```
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzsWt9zozgS_muUF1VcIECGhzzYzvh2ayc3qUlq6t5SMsi2boTESSKJ96-_kgCDMPnh3KZqautSuxMM3V-3vv7UtCFEa7YTlF6BZAmS6wtSm71UV4XJn_88PF1sZHG4-k4rJYs6pwpECxAsAA7a_4IFiJZwwwRAa1kZeFkRrakG0TUlih8uc02hota1mHEOL--sR7Ao6JYJClmEIIiDbS3yBxTMAUpZiCFASfWAgnSWS6pyCtCqMURJLsXj4GPgjnFsj0N7XBnlvAHKIJgvQbCgwqhDkzTsEEIIomv4J302cCIcNNLiDx2ixkM7jz4TZ4njo2VZzZgzZHlZQfqfLrUGwuYXdLbPUjlL-3u0ttDZaCMV7S49S-WvbgUJZzsBh7HRMLgmJbVlhfXOS9llEYWdm96rGcNBtzxOc0tJD9hxHYxqEA7YKSwCcghE75vluDADfGveumJ7InLmRtUiH8C2SJbVEA_5R3EydHihZmnnUtZ8xjBKnU9Zc8hSeBlaea0GiH6A-aDCqQcyKnKTptVXdA1zwnlT5Tjg_LGc6ZKJmTVHqT09FGgbB6BsWLQ4GxSNm4FxE8ZTjYNIPPkOcE7UGM4YjoIe_3UtCKKUfLIu03Jo0N5URFPyCA2SbKyG-JOcRo0quBPRgLPEV9Nga5YVStIRf9P940ghmiIvSceiKyuEwxFzIT7q2usOCEdToPhkmWUVxbHfIN7I1nWOVvw-vEUaNCqvXbReb7UMa5WcdrZglLauN1bR4bTga9f1cPyK6CNbwMwP6zWAxvQYxy9F1O_ihqwWwAa5DH3U5KSxRxM1SPBQMtTFDwe9IUoSH3Y-xX-Cp24USTbZ2RyI16PsyRnDSTDuOx2MDx6_uIs9vTQ7pBU5H3djZ94TkXk3DH5E7UD6mxFAiVSzZpue9obY1TuEW8I1bY-PEfrMbDttq6n3fLgEx4MXLTll8QgwptG2jpYfL61jxi6ltJWl49ivLw7RRBFa2L4MR3M0Id5wVK9GYvKUfxvthFPcLnhcCew3g7KKvJL5QrCJefYtfNz62GTCHqfNaZjDSEX4RU7jiclgPBK0u-Y4EgzkOgjhzU74pJl7o0Eyn9A6DiZvVg7szRzbFv_C2IL9NownRNnj9E0LoIQU7izqeccjEYwUmA4E2DSuI8RAV4qOCm63AZhfjwfywbGsDIhsTuuCGALQ-s_DE0Br27ovKyX_TXPTfgRozUTO64L2JxbX9wCtr6nQ9IZUsz2IFnGYWcBHyQrorKIFiBadyZJoCqLVNVXskRb3dsl_0IP7_YPwmnZnfhdb6Y6Xdf6TmnsQfWmASvlI10qW33jRXNIApZ0RWgxd7KcMgmT5xMwediGbzneSGIhWYL4kQopDKWttSXPX71hZcepys9i9410uK1r8RvT-nmycxdkQ7amFXVyT-mleloj3AFuIoX9BDWHcx7olTP0C64y-QFfOpSu9q8fby1u2-hiV7xOyWx7194JUzihJtOzUOML6pcsDEusCF1pTZZgU0LYKFK5lLYofhEOAMEC2CaE_6AESrigpDpAJKOgTLO1eWgOEAJrDLWGcFjMQLG6_flncfYG63pTMQAI39Q4qWkllbAPbG1Npmw1aA7TeMbOvN7Ncln2nGTUkpnVNNUBrSEQB274EzZ7CXBG9hxuS_zSK5NTGvjMk_wmLuqya7_nBDLqfWyV3ipSQqF1dUmH0i51wUzNeALR-72MMECzCNsj3WggmdtDaW8q2tcgtqQClR09bMkt-BhCCUsBSFjWn1noAiWyPRy-gnkA5nC5WF7d5hNIOK1EAg-cgCIL5drvdzgu6TSM0kIU-6ObgVjFhHIf3llGA0t5IkacHqY2ipHSqWEEmjGu7KH0Hk7OZPc82zb9fv_64uasrK4qZljMUzIIdMwAtg-fQZdd-SwAoCke55xndTuX-vRZ3bCcI_42IglOlXV6fkJ5NoE8PjdPbRAn0ErFfhRqmmtN6lldWnoH7v0GJPJQ0RgkK2sybpJ5T_IDjS85E_Xy5E3VzIbfZYZeXc-nTin3ADGfbHFZmbzfww0_G-Xnozr9HT8bpxnMMd9ot79y04znugbEPjNL5NoJkY3vHWbDOsYedn8CGm7MBw00PmPqAUUYzfB6gc-kBsyFgTLdkntAXZheUHjs-FKSkunJbNfvQ7eODYOfMM2eFsMPkWRPOL8iGnQbaGXan5BNAaS3cc_Wia5lfbA9f3X0ZdQLb7YKREDZFQl7O-69I-pOL953mh5wzsVtwLnNipC1bf3lZl9WtUceLv5cV9wxuiL3UO6MVjIMM19w_ClFa85Pgn1fmFYxQE7mN25WcCTtL_S6MdMG9e-goncbg_yX8hUrYkPl-eJhLoU07EJ3GGVx-ddeHo11fbMPsrSw6uOZTpWROtf6nLHzJXcvyXlFqz7ffyAeFI5rlSy7zn93SXdAZ04rMgjdSRqOUKd0m56WsatHOaK-E8SajeBsE8wwPiO48b4nWQ9TeYn2cwkc1WgjCD5rpGyLIjvqSPjpZXvCHxsiJiTInnKhvldEnQ6VbVjMN2EV70xvGaRzFyQv3Q7vwG1lQPp2_t2KPrA9xEX351Um-dV_WxgQ7Bnt-vfk1SinF0fARluP0tYT_ptytpKJj5pAjp6fOn9ADksV_iTQ_jfK_aan-leKVLOg_qBgXzFWkr9d8JPUco3SQ-I17_nAvuyRtHRYFqdw9foqCxuEsAlqXz1eqXVu_8nSsVBqcp9Ruqat38vUBQl4S2q_B8msio8FAZNlIZAVK39NPpwj-O_A2rU5LypEy5D-S22abkG4GGavaSeuWVZQzMfoWYRQTu-90OyXNk7XfE7Wj5obke4ezmLr6lW0UUe5RuBveT6yk5N9qU9VmzfgEyP90-YXlLJQiB3t2WCzHCa93TJz29t5em6I5d3wCG63cWyqPRou1tEWlqin91B1DVubBSNn2iWYVfzBRvGb1gyq2ZVR1dht75ezfH39y-a0y14o9UnWiwTikm16C_pPVLUlwmEFZmRvCxCcEpzjM-uBo9EguK7Izn3g6lx4wGgPSOIAPD9bnQRuizEPZr-vdIWg8CNGN5Un3E2QJbMDfyZesuoE_a9vnYiOVoU6auVTUvbugXZ_o3t5eFFdRkUUZuaBX4TyKwyDBCbrYX6E8y2OSFgEhGKM0RNsIERylGxyQmGbogl2hAMUhCqMQB0GCZlGazglOA4K2KcrnBMQBLQnjM_cnPFLtLtwLl6swzNIsuuBkQ7l2fw-KkHvhcinF5SPhrHAvflYAoXYfGEWE3kpVanslub5QVy0DOw3igDNtdB_FMMPd35kevxMm13_he6iLWvGrj79ralf_eIX-GwAA___dbrD3">