[CodeGen] Fix incorrectly detected reduction bug in ComplexDeinterleaving pass

[igor.kirillov]

Summary

Using ACLE intrinsics, it is possible to create a loop that the
deinterleaving pass incorrectly classified as a reduction loop.
For example, for fixed-width vectors the loop was like below:

vector.body:

%a = phi <4 x float> [ %init.a, %entry ], [ %updated.a, %vector.body ]
%b = phi <4 x float> [ %init.b, %entry ], [ %updated.b, %vector.body ]
...

; Does not depend on %a or %b:

%updated.a = ...
%updated.b = ...

[mgabka]

Could you improve commit message description as well?

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

241

there is no attribute like that, I guess it can be removed, or if attribute was relevant for this test it needs to be added

241

I have a general comment about this test, to me looks like it can be simplified and do not use the aarch64 specific intrinsics, isn't it the case that we have only fadd here but no load/store instructions?

[igor.kirillov]

Update test and commit message

[glandium]

That fixes the crash for me.

[mgabka]

In the proposed new commit message you mention neon, but to me looks like the bug isn't neon specific, and could be triggered by scalable vectors, am I correct?
shall we have a separate test for scalable vectors?

If that is correct could you adjust the commit message?

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

241

Thanks Igor for adjusting the test, I have a few more comments/requests:

1. Could you change the function name to something more descriptive? Like incorrect_reduction_pattern or something similar
2. remove the numbers fro, variable names (it will make it easier to read)

[igor.kirillov]

Update test and commit message

[igor.kirillov]

I adjusted the commit message rather than adding a test. It doesn't matter if vectors are scalable or fixed-width cause code that processes PHINodes does not behave differently. So I think adding a scalable test doesn't add more coverage.

[mgabka]

Hi Igor,
"Advanced SIMD" in aarch64 means neon.

Could you change the commit message to something like:

By using ACLE intrinsics, it is possible to create a loop that the deinterleaving pass incorrectly classified as a reduction loop.
For example for fixed width vectors the loop was like below:

vector.body:

%a = phi <4 x float> [ %init.a, %entry ], [ %updated.a, %vector.body ]
%b = phi <4 x float> [ %init.b, %entry ], [ %updated.b, %vector.body ]
...
; Does not depend on %a or %b:

%updated.a = ...
%updated.b = ...

[igor.kirillov]

Rebase and update commit message

llvm/lib/CodeGen/ComplexDeinterleavingPass.cpp

private:
   /// %ReductionOP, which we refer to as real and imag (or vice versa), and
   /// traverse the use-tree to detect complex operations. As this is a reduction
   /// operation, it will eventually reach RealPHI and ImagPHI, which corresponds
   /// to the %ReductionOPs that we suspect to be complex.
   /// RealPHI and ImagPHI are used by the identifyPHINode method.
   PHINode *RealPHI = nullptr;
   PHINode *ImagPHI = nullptr;
 
+  /// Set this flag to true if RealPHI and ImagPHI were reached during reduction
+  /// detection.
+  bool PHIsFound = false;
+
   /// OldToNewPHI maps the original real PHINode to a new, double-sized PHINode.
   /// The new PHINode corresponds to a vector of deinterleaved complex numbers.
   /// This mapping is populated during
   /// ComplexDeinterleavingOperation::ReductionPHI node replacement. It is then
   /// used in the ComplexDeinterleavingOperation::ReductionOperation node
   /// replacement process.
   std::map<PHINode *, PHINode *> OldToNewPHI;
 
for (auto &PHI : B->phis()) {
     auto NumUsers = 0u;
     for (auto *U : ReductionOp->users()) {
       ++NumUsers;
       if (U == &PHI)
         continue;
       FinalReduction = dyn_cast<Instruction>(U);
     }
 
-    if (NumUsers != 2 || !FinalReduction || FinalReduction->getParent() == B)
+    if (NumUsers != 2 || !FinalReduction || FinalReduction->getParent() == B ||
+        isa<PHINode>(FinalReduction))
       continue;
 
     ReductionInfo[ReductionOp] = {&PHI, FinalReduction};
     BackEdge = B;
     auto BackEdgeIdx = PHI.getBasicBlockIndex(B);
     auto IncomingIdx = BackEdgeIdx == 0 ? 1 : 0;
     Incoming = PHI.getIncomingBlock(IncomingIdx);
     FoundPotentialReduction = true;
for (size_t j = i + 1; j < OperationInstruction.size(); ++j) {
 
       auto *Real = OperationInstruction[i];
       auto *Imag = OperationInstruction[j];
       if (Real->getType() != Imag->getType())
         continue;
 
       RealPHI = ReductionInfo[Real].first;
       ImagPHI = ReductionInfo[Imag].first;
+      PHIsFound = false;
       auto Node = identifyNode(Real, Imag);
       if (!Node) {
         std::swap(Real, Imag);
         std::swap(RealPHI, ImagPHI);
         Node = identifyNode(Real, Imag);
       }
 
-      // If a node is identified, mark its operation instructions as used to
-      // prevent re-identification and attach the node to the real part
-      if (Node) {
+      // If a node is identified and reduction PHINode is used in the chain of
+      // operations, mark its operation instructions as used to prevent
+      // re-identification and attach the node to the real part
+      if (Node && PHIsFound) {
         LLVM_DEBUG(dbgs() << "Identified reduction starting from instructions: "
                           << *Real << " / " << *Imag << "\n");
         Processed[i] = true;
         Processed[j] = true;
         auto RootNode = prepareCompositeNode(
             ComplexDeinterleavingOperation::ReductionOperation, Real, Imag);
         RootNode->addOperand(Node);
         RootToNode[Real] = RootNode;

 }
 
 ComplexDeinterleavingGraph::NodePtr
 ComplexDeinterleavingGraph::identifyPHINode(Instruction *Real,
                                             Instruction *Imag) {
   if (Real != RealPHI || Imag != ImagPHI)
     return nullptr;
 
+  PHIsFound = true;
   NodePtr PlaceholderNode = prepareCompositeNode(
       ComplexDeinterleavingOperation::ReductionPHI, Real, Imag);
   return submitCompositeNode(PlaceholderNode);
 }
 
 ComplexDeinterleavingGraph::NodePtr
 ComplexDeinterleavingGraph::identifySelectNode(Instruction *Real,
                                                Instruction *Imag) {

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

middle.block:                                     ; preds = %vector.body
   %bin.rdx40 = fadd fast <2 x double> %11, %10
   %17 = tail call fast double @llvm.vector.reduce.fadd.v2f64(double -0.000000e+00, <2 x double> %bin.rdx40)
   %bin.rdx = fadd fast <2 x double> %15, %14
   %18 = tail call fast double @llvm.vector.reduce.fadd.v2f64(double -0.000000e+00, <2 x double> %bin.rdx)
   %.fca.0.0.insert = insertvalue %"struct.std::complex" poison, double %17, 0, 0
   %.fca.0.1.insert = insertvalue %"struct.std::complex" %.fca.0.0.insert, double %18, 0, 1
   ret %"struct.std::complex" %.fca.0.1.insert
 }
+
+; The reduced bug from D153355. Shows that reduction was detected where it did not exist.
+define void @incorrect_reduction_pattern(i1 %exitcond.not) {
+; CHECK-LABEL: incorrect_reduction_pattern:
+; CHECK:       // %bb.0: // %entry
+; CHECK-NEXT:  .LBB3_1: // %for.body
+; CHECK-NEXT:    // =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    tbz w0, #0, .LBB3_1
+; CHECK-NEXT:  // %bb.2: // %for.end.loopexit
+; CHECK-NEXT:    ret
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %for.body, %entry
+  %vec_r = phi <4 x float> [ zeroinitializer, %entry ], [ %lane_r, %for.body ]
+  %vec_i = phi <4 x float> [ zeroinitializer, %entry ], [ %lane_i, %for.body ]
+  %add = fadd <4 x float> %vec_r, %vec_i
+  %lane_r = shufflevector <4 x float> <float 1.000000e+00, float undef, float undef, float undef>, <4 x float> zeroinitializer, <4 x i32> zeroinitializer
+  %lane_i = shufflevector <4 x float> <float 1.000000e+00, float undef, float undef, float undef>, <4 x float> zeroinitializer, <4 x i32> zeroinitializer
+  br i1 %exitcond.not, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:                                 ; preds = %for.body
+  %mul.r = fadd <4 x float> %lane_r, %add
+  %mul.i = fadd <4 x float> %lane_i, %add
+  ret void
+}
+
 declare double @llvm.vector.reduce.fadd.v2f64(double, <2 x double>)