AArch64 infinite recursion at llvm::DAGTypeLegalizer::RemapId(unsigned int&)

[DataCorrupted]

When compiling the following piece of code, AARch64 will fall into an infinite loop. While x64_64 is fine with it.

Reproduce

llc -mtriple=aarch64 <filename>
llc -mtriple=x86_64 <filename>

; ModuleID = 'aarch64-dag-crashes/id:000001,sig:11,src:016155+013757,time:72939681,execs:21049155,op:libAFLCustomIRMutator.so,pos:0'
source_filename = "M"

define void @f() {
BB:
  %A3 = alloca i16, align 2
  %A2 = alloca i16, align 2
  %A = alloca <4 x i16>, align 8
  %L = load <4 x i16>, <4 x i16>* %A, align 8
  %B = sub <4 x i16> %L, %L
  %B1 = srem <4 x i16> %B, %B
  %E = extractelement <4 x i16> %B, i8 0
  %I = insertelement <4 x i16> %B1, i16 %E, i16 0
  store <4 x i16> %I, <4 x i16>* %A, align 8
  %E1 = extractelement <4 x i16> %I, i16 %E
  store i16 %E1, i16* %A2, align 2
  %E2 = extractelement <4 x i16> %B, i16 %E1
  %E3 = extractelement <4 x i16> %I, i16 %E2
  store i16 %E3, i16* %A3, align 2
  ret void
}

Error message

PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.      Program arguments: .../llvm-project/build-debug/bin/llc -mtriple=aarch64 id:000001,sig:11,src:016155+013757,time:72939681,execs:21049155,op:libAFLCustomIRMutator.so,pos:0.ll
1.      Running pass 'Function Pass Manager' on module 'id:000001,sig:11,src:016155+013757,time:72939681,execs:21049155,op:libAFLCustomIRMutator.so,pos:0.ll'.
2.      Running pass 'AArch64 Instruction Selection' on function '@f'
  #0 0x00000000030fa65a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) .../llvm-project/llvm/lib/Support/Unix/Signals.inc:569:11
  #1 0x00000000030fa80b PrintStackTraceSignalHandler(void*) .../llvm-project/llvm/lib/Support/Unix/Signals.inc:636:1
  #2 0x00000000030f8e56 llvm::sys::RunSignalHandlers() .../llvm-project/llvm/lib/Support/Signals.cpp:103:5
  #3 0x00000000030faf35 SignalHandler(int) .../llvm-project/llvm/lib/Support/Unix/Signals.inc:407:1
  #4 0x00007f6a59964980 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12980)
  #5 0x0000000002f1f5f8 llvm::SmallDenseMap<unsigned int, unsigned int, 8u, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>::getBuckets() const .../llvm-project/llvm/include/llvm/ADT/DenseMap.h:1160:0
  #6 0x0000000002f1f595 llvm::DenseMapBase<llvm::SmallDenseMap<unsigned int, unsigned int, 8u, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>, unsigned int, unsigned int, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>::getBuckets() const .../llvm-project/llvm/include/llvm/ADT/DenseMap.h:517:5
  #7 0x0000000002f1f391 bool llvm::DenseMapBase<llvm::SmallDenseMap<unsigned int, unsigned int, 8u, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>, unsigned int, unsigned int, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>::LookupBucketFor<unsigned int>(unsigned int const&, llvm::detail::DenseMapPair<unsigned int, unsigned int> const*&) const .../llvm-project/llvm/include/llvm/ADT/DenseMap.h:610:33
  #8 0x0000000002f1f2d5 bool llvm::DenseMapBase<llvm::SmallDenseMap<unsigned int, unsigned int, 8u, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>, unsigned int, unsigned int, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>::LookupBucketFor<unsigned int>(unsigned int const&, llvm::detail::DenseMapPair<unsigned int, unsigned int>*&) .../llvm-project/llvm/include/llvm/ADT/DenseMap.h:661:10
  #9 0x0000000002f1ad9d llvm::DenseMapBase<llvm::SmallDenseMap<unsigned int, unsigned int, 8u, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>, unsigned int, unsigned int, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, unsigned int>>::find(unsigned int const&) .../llvm-project/llvm/include/llvm/ADT/DenseMap.h:152:9
 #10 0x0000000002f1756c llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:585:27
 #11 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
 #12 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
 #13 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
......
#253 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
#254 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
#255 0x0000000002f17617 llvm::DAGTypeLegalizer::RemapId(unsigned int&) .../llvm-project/llvm/lib/CodeGen/SelectionDAG/LegalizeTypes.cpp:591:10
Segmentation fault

This has been observed on LLVM-14 and latest commit cfd2c5c.

Some analysis

Problem starts from LegalizeTypes.cpp:697

void DAGTypeLegalizer::ReplaceValueWith(SDValue From, SDValue To) {
         .....
          DAG.ReplaceAllUsesOfValueWith(OldVal, NewVal);
          if (OldValId != NewValId)
            ReplacedValues[OldValId] = NewValId;
}

 void NoteDeletion(SDNode *Old, SDNode *New) {
      if (OldId != NewId) {
        ReplacedValues[OldId] = NewId;
        .......
      }
}

For some reason, ReplaceAllUsesOfValueWith(...) eventually calls NoteDeletion(...). But by then OldVal and NewVal are switched.
Therefore, when NoteDeletion(...) in LegalizeTypes.h:185 are called, a reversed relation is added to ReplacedValues.
After ReplaceAllUsesOfValueWith(...), the original relation is also added to ReplacedValues, causing a loop, and later resulting infinite recursion.

My stack trace vagelly look like this when ReplacedValues is incorrectly updated :

    frame #0: 0x0000000002f1f848 llc`llvm::DAGTypeLegalizer::NoteDeletion(this=0x00007fffffffa698, Old=0x0000000006174c40, New=0x0000000006174b70) at LegalizeTypes.h:209:9
    frame #1: 0x0000000002f1b11f llc`(anonymous namespace)::NodeUpdateListener::NodeDeleted(this=0x00007fffffff9e80, N=0x0000000006174c40, E=0x0000000006174b70) at LegalizeTypes.cpp:631:9
    frame #2: 0x0000000002df541c llc`llvm::SelectionDAG::AddModifiedNodeToCSEMaps(this=0x00000000060fa2c0, N=0x0000000006174c40) at SelectionDAG.cpp:1173:14
    frame #3: 0x0000000002df585a llc`llvm::SelectionDAG::ReplaceAllUsesWith(this=0x00000000060fa2c0, From=0x0000000006174bd8, To=0x0000000006174968) at SelectionDAG.cpp:10311:5
    frame #4: 0x0000000002df53f0 llc`llvm::SelectionDAG::AddModifiedNodeToCSEMaps(this=0x00000000060fa2c0, N=0x0000000006174bd8) at SelectionDAG.cpp:1169:7
    frame #5: 0x0000000002e3ac23 llc`llvm::SelectionDAG::ReplaceAllUsesWith(this=0x00000000060fa2c0, FromN=SDValue @ 0x00007fffffff9ae0, To=SDValue @ 0x00007fffffff9ad0) at SelectionDAG.cpp:10250:5
    frame #6: 0x0000000002e37c6d llc`llvm::SelectionDAG::ReplaceAllUsesOfValueWith(this=0x00000000060fa2c0, From=SDValue @ 0x00007fffffff9be0, To=SDValue @ 0x00007fffffff9bd0) at SelectionDAG.cpp:10378:5
    frame #7: 0x0000000002f17961 llc`llvm::DAGTypeLegalizer::ReplaceValueWith(this=0x00007fffffffa698, From=SDValue @ 0x00007fffffff9fe0, To=SDValue @ 0x00007fffffff9fd0) at LegalizeTypes.cpp:732:15
    frame #8: 0x0000000002fa7949 llc`llvm::DAGTypeLegalizer::PromoteIntegerOperand(this=0x00007fffffffa698, N=0x00000000061746f8, OpNo=0) at LegalizeIntegerTypes.cpp:1754:3
    frame #9: 0x0000000002f16337 llc`llvm::DAGTypeLegalizer::run(this=0x00007fffffffa698) at LegalizeTypes.cpp:336:30

I'll keep working on it to provide more info. However, there are some Legalize details I am not really familiar with. If anyone can point me where to get more detail about Legalizer it'd be best.

[llvmbot]

@llvm/issue-subscribers-backend-aarch64

[DataCorrupted]

https://godbolt.org/z/rKv56aa8d

This problems still exists.