[SLP] Add support for swapping icmp/fcmp predicates to permit vectorization

[RKSimon]

Summary

We should be able to match elements with the swapped predicate as well - as long as we commute the source operands.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

1860 ↗

(On Diff #192699)

CmpInst *->auto *. You need always to add & or * to the auto (if any can be applied) to make it easier to read the code.

1861 ↗

(On Diff #192699)

Better to use Value * here because it is not easy to deduce the type from the operation.

1862 ↗

(On Diff #192699)

Same here

[RKSimon]

Addressed @ABataev 's comments

[ABataev]

LG

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::BitCast: {
         buildTree_rec(Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::ICmp:
     case Instruction::FCmp: {
       // Check that all of the compares have the same predicate.
       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
+      CmpInst::Predicate SwapP0 = CmpInst::getSwappedPredicate(P0);
       Type *ComparedTy = VL0->getOperand(0)->getType();
       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
         CmpInst *Cmp = cast<CmpInst>(VL[i]);
-        if (Cmp->getPredicate() != P0 ||
+        if ((Cmp->getPredicate() != P0 && Cmp->getPredicate() != SwapP0) ||
             Cmp->getOperand(0)->getType() != ComparedTy) {
           BS.cancelScheduling(VL, VL0);
           newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs()
                      << "SLP: Gathering cmp with different predicate.\n");
           return;
         }
       }
 
       newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 
-      for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
-        ValueList Operands;
-        // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
-
-        UserTreeIdx.EdgeIdx = i;
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+      // Collect operands - commute if it uses the swapped predicate.
+      ValueList Left, Right;
+      for (Value *V : VL) {
+        auto *Cmp = cast<CmpInst>(V);
+        Value *LHS = Cmp->getOperand(0);
+        Value *RHS = Cmp->getOperand(1);
+        if (Cmp->getPredicate() != P0)
+          std::swap(LHS, RHS);
+        Left.push_back(LHS);
+        Right.push_back(RHS);
       }
+
+      UserTreeIdx.EdgeIdx = 0;
+      buildTree_rec(Left, Depth + 1, UserTreeIdx);
+      UserTreeIdx.EdgeIdx = 1;
+      buildTree_rec(Right, Depth + 1, UserTreeIdx);
       return;
     }
     case Instruction::Select:
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:

llvm/trunk/test/Transforms/SLPVectorizer/X86/cmp_commute.ll

 }
 
 ;
 ; Check that we can commute operands by swapping the predicate.
 ;
 
 define <4 x i32> @icmp_sgt_slt_v4i32(<4 x i32> %a, i32* %b) {
 ; CHECK-LABEL: @icmp_sgt_slt_v4i32(
-; CHECK-NEXT:    [[A0:%.*]] = extractelement <4 x i32> [[A:%.*]], i32 0
-; CHECK-NEXT:    [[A1:%.*]] = extractelement <4 x i32> [[A]], i32 1
-; CHECK-NEXT:    [[A2:%.*]] = extractelement <4 x i32> [[A]], i32 2
-; CHECK-NEXT:    [[A3:%.*]] = extractelement <4 x i32> [[A]], i32 3
-; CHECK-NEXT:    [[P1:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 1
-; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 2
-; CHECK-NEXT:    [[P3:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 3
-; CHECK-NEXT:    [[B0:%.*]] = load i32, i32* [[B]], align 4
-; CHECK-NEXT:    [[B1:%.*]] = load i32, i32* [[P1]], align 4
-; CHECK-NEXT:    [[B2:%.*]] = load i32, i32* [[P2]], align 4
-; CHECK-NEXT:    [[B3:%.*]] = load i32, i32* [[P3]], align 4
-; CHECK-NEXT:    [[C0:%.*]] = icmp sgt i32 [[A0]], [[B0]]
-; CHECK-NEXT:    [[C1:%.*]] = icmp slt i32 [[B1]], [[A1]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp slt i32 [[B2]], [[A2]]
-; CHECK-NEXT:    [[C3:%.*]] = icmp sgt i32 [[A3]], [[B3]]
-; CHECK-NEXT:    [[D0:%.*]] = insertelement <4 x i1> undef, i1 [[C0]], i32 0
-; CHECK-NEXT:    [[D1:%.*]] = insertelement <4 x i1> [[D0]], i1 [[C1]], i32 1
-; CHECK-NEXT:    [[D2:%.*]] = insertelement <4 x i1> [[D1]], i1 [[C2]], i32 2
-; CHECK-NEXT:    [[D3:%.*]] = insertelement <4 x i1> [[D2]], i1 [[C3]], i32 3
-; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[D3]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[B:%.*]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x i32>, <4 x i32>* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp slt <4 x i32> [[TMP2]], [[A:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[TMP3]] to <4 x i32>
 ; CHECK-NEXT:    ret <4 x i32> [[R]]
 ;
   %a0 = extractelement <4 x i32> %a, i32 0
   %a1 = extractelement <4 x i32> %a, i32 1
   %a2 = extractelement <4 x i32> %a, i32 2
   %a3 = extractelement <4 x i32> %a, i32 3
   %p0 = getelementptr inbounds i32, i32* %b, i32 0
   %p1 = getelementptr inbounds i32, i32* %b, i32 1
;
   %d2 = insertelement <4 x i1>   %d1, i1 %c2, i32 2
   %d3 = insertelement <4 x i1>   %d2, i1 %c3, i32 3
   %r = sext <4 x i1> %d3 to <4 x i32>
   ret <4 x i32> %r
 }
 
 define <4 x i32> @icmp_uge_ule_v4i32(<4 x i32> %a, i32* %b) {
 ; CHECK-LABEL: @icmp_uge_ule_v4i32(
-; CHECK-NEXT:    [[A0:%.*]] = extractelement <4 x i32> [[A:%.*]], i32 0
-; CHECK-NEXT:    [[A1:%.*]] = extractelement <4 x i32> [[A]], i32 1
-; CHECK-NEXT:    [[A2:%.*]] = extractelement <4 x i32> [[A]], i32 2
-; CHECK-NEXT:    [[A3:%.*]] = extractelement <4 x i32> [[A]], i32 3
-; CHECK-NEXT:    [[P1:%.*]] = getelementptr inbounds i32, i32* [[B:%.*]], i64 1
-; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 2
-; CHECK-NEXT:    [[P3:%.*]] = getelementptr inbounds i32, i32* [[B]], i64 3
-; CHECK-NEXT:    [[B0:%.*]] = load i32, i32* [[B]], align 4
-; CHECK-NEXT:    [[B1:%.*]] = load i32, i32* [[P1]], align 4
-; CHECK-NEXT:    [[B2:%.*]] = load i32, i32* [[P2]], align 4
-; CHECK-NEXT:    [[B3:%.*]] = load i32, i32* [[P3]], align 4
-; CHECK-NEXT:    [[C0:%.*]] = icmp uge i32 [[A0]], [[B0]]
-; CHECK-NEXT:    [[C1:%.*]] = icmp ule i32 [[B1]], [[A1]]
-; CHECK-NEXT:    [[C2:%.*]] = icmp ule i32 [[B2]], [[A2]]
-; CHECK-NEXT:    [[C3:%.*]] = icmp uge i32 [[A3]], [[B3]]
-; CHECK-NEXT:    [[D0:%.*]] = insertelement <4 x i1> undef, i1 [[C0]], i32 0
-; CHECK-NEXT:    [[D1:%.*]] = insertelement <4 x i1> [[D0]], i1 [[C1]], i32 1
-; CHECK-NEXT:    [[D2:%.*]] = insertelement <4 x i1> [[D1]], i1 [[C2]], i32 2
-; CHECK-NEXT:    [[D3:%.*]] = insertelement <4 x i1> [[D2]], i1 [[C3]], i32 3
-; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[D3]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32* [[B:%.*]] to <4 x i32>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x i32>, <4 x i32>* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ule <4 x i32> [[TMP2]], [[A:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[TMP3]] to <4 x i32>
 ; CHECK-NEXT:    ret <4 x i32> [[R]]
 ;
   %a0 = extractelement <4 x i32> %a, i32 0
   %a1 = extractelement <4 x i32> %a, i32 1
   %a2 = extractelement <4 x i32> %a, i32 2
   %a3 = extractelement <4 x i32> %a, i32 3
   %p0 = getelementptr inbounds i32, i32* %b, i32 0
   %p1 = getelementptr inbounds i32, i32* %b, i32 1
;
   %d2 = insertelement <4 x i1>   %d1, i1 %c2, i32 2
   %d3 = insertelement <4 x i1>   %d2, i1 %c3, i32 3
   %r = sext <4 x i1> %d3 to <4 x i32>
   ret <4 x i32> %r
 }
 
 define <4 x i32> @fcmp_ogt_olt_v4i32(<4 x float> %a, float* %b) {
 ; CHECK-LABEL: @fcmp_ogt_olt_v4i32(
-; CHECK-NEXT:    [[A0:%.*]] = extractelement <4 x float> [[A:%.*]], i32 0
-; CHECK-NEXT:    [[A1:%.*]] = extractelement <4 x float> [[A]], i32 1
-; CHECK-NEXT:    [[A2:%.*]] = extractelement <4 x float> [[A]], i32 2
-; CHECK-NEXT:    [[A3:%.*]] = extractelement <4 x float> [[A]], i32 3
-; CHECK-NEXT:    [[P1:%.*]] = getelementptr inbounds float, float* [[B:%.*]], i64 1
-; CHECK-NEXT:    [[P2:%.*]] = getelementptr inbounds float, float* [[B]], i64 2
-; CHECK-NEXT:    [[P3:%.*]] = getelementptr inbounds float, float* [[B]], i64 3
-; CHECK-NEXT:    [[B0:%.*]] = load float, float* [[B]], align 4
-; CHECK-NEXT:    [[B1:%.*]] = load float, float* [[P1]], align 4
-; CHECK-NEXT:    [[B2:%.*]] = load float, float* [[P2]], align 4
-; CHECK-NEXT:    [[B3:%.*]] = load float, float* [[P3]], align 4
-; CHECK-NEXT:    [[C0:%.*]] = fcmp ogt float [[A0]], [[B0]]
-; CHECK-NEXT:    [[C1:%.*]] = fcmp olt float [[B1]], [[A1]]
-; CHECK-NEXT:    [[C2:%.*]] = fcmp olt float [[B2]], [[A2]]
-; CHECK-NEXT:    [[C3:%.*]] = fcmp ogt float [[A3]], [[B3]]
-; CHECK-NEXT:    [[D0:%.*]] = insertelement <4 x i1> undef, i1 [[C0]], i32 0
-; CHECK-NEXT:    [[D1:%.*]] = insertelement <4 x i1> [[D0]], i1 [[C1]], i32 1
-; CHECK-NEXT:    [[D2:%.*]] = insertelement <4 x i1> [[D1]], i1 [[C2]], i32 2
-; CHECK-NEXT:    [[D3:%.*]] = insertelement <4 x i1> [[D2]], i1 [[C3]], i32 3
-; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[D3]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast float* [[B:%.*]] to <4 x float>*
+; CHECK-NEXT:    [[TMP2:%.*]] = load <4 x float>, <4 x float>* [[TMP1]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = fcmp olt <4 x float> [[TMP2]], [[A:%.*]]
+; CHECK-NEXT:    [[R:%.*]] = sext <4 x i1> [[TMP3]] to <4 x i32>
 ; CHECK-NEXT:    ret <4 x i32> [[R]]
 ;
   %a0 = extractelement <4 x float> %a, i32 0
   %a1 = extractelement <4 x float> %a, i32 1
   %a2 = extractelement <4 x float> %a, i32 2
   %a3 = extractelement <4 x float> %a, i32 3
   %p0 = getelementptr inbounds float, float* %b, i32 0
   %p1 = getelementptr inbounds float, float* %b, i32 1