[CodeGen] Fix incorrect insertion point selection for reduction nodes in ComplexDeinterleavingPass

[igor.kirillov]

Summary

When replacing ComplexDeinterleavingPass::ReductionOperation, we can do it
either from the Real or Imaginary part. The correct way is to take whichever
is later in the BasicBlock, but before the patch, we just always took the
Real part.

Fixes https://github.com/llvm/llvm-project/issues/65044

[danilaml]

Not exactly familiar with this part of code, but the fix makes sense to me.
Perhaps we could add a check that OrderedRoots is topologically sorted under EXPENSIVE_CHECKS.

[igor.kirillov]

@danilaml OrderedRoots has Instructions from the same BasicBlock, and they get there one by one during for (auto &I : *B) iteration. So, there is no risk of messing up there unless someone tries to add much more functionality :)

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

 }
 
 bool ComplexDeinterleavingGraph::identifyNodes(Instruction *RootI) {
   // This potential root instruction might already have been recognized as
   // reduction. Because RootToNode maps both Real and Imaginary parts to
   // CompositeNode we should choose only one either Real or Imag instruction to
   // use as an anchor for generating complex instruction.
   auto It = RootToNode.find(RootI);
-  if (It != RootToNode.end() && It->second->Real == RootI) {
+  if (It != RootToNode.end()) {
+    auto RootNode = It->second;
+    assert(RootNode->Operation ==
+           ComplexDeinterleavingOperation::ReductionOperation);
+    // Find out which part, Real or Imag, comes later, and only if we come to
+    // the latest part, add it to OrderedRoots.
+    auto *R = cast<Instruction>(RootNode->Real);
+    auto *I = cast<Instruction>(RootNode->Imag);
+    auto *ReplacementAnchor = R->comesBefore(I) ? I : R;
+    if (ReplacementAnchor != RootI)
+      return false;
     OrderedRoots.push_back(RootI);
     return true;
   }
 
   auto RootNode = identifyRoot(RootI);
   if (!RootNode)
     return false;
 

llvm/test/CodeGen/AArch64/complex-deinterleaving-crash.ll

-; XFAIL: *
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py UTC_ARGS: --version 2
 ; RUN: llc %s --mattr=+complxnum -o - | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "aarch64-none-linux-gnu"
 
 ; Check that deinterleaving pass doesn't generate broken IR
 define void @check_deinterleave_crash() #0 {
+; CHECK-LABEL: check_deinterleave_crash:
+; CHECK:       // %bb.0: // %bb
+; CHECK-NEXT:    mov x8, xzr
+; CHECK-NEXT:    str wzr, [x8]
 bb:
   br label %bb173
 
 bb173:                                            ; preds = %bb173, %bb
   %phi177 = phi <2 x i32> [ %add190, %bb173 ], [ zeroinitializer, %bb ]
   %phi178 = phi <2 x i32> [ %add187, %bb173 ], [ zeroinitializer, %bb ]
   %add185 = add <2 x i32> %phi178, <i32 1, i32 1>
   %add186 = add <2 x i32> %phi177, <i32 1, i32 1>