[SLP] Fix regression in broadcasts caused by operand reordering patch D59973.

[vporpo]

Summary

This patch fixes a regression caused by the operand reordering refactoring patch https://reviews.llvm.org/D59973 .
The fix changes the strategy to Splat instead of Opcode, if broadcast opportunities are found.
Please see the lit test for some examples.

[vporpo]

Minor comment update.

[RKSimon]

@vporpo I've committed the test case with current codegen at rL361805 - please can you rebase so this patch shows the codegen delta?

[vporpo]

Thanks for committing the test @RKSimon . I will follow up on this soon.

[vporpo]

Rebased.

[RKSimon]

@ABataev @dtemirbulatov any comments?

[ABataev]

test/Transforms/SLPVectorizer/X86/broadcast.ll

18–28

Hmm, it is very strange that the new result is more cost effective than the previous one. We change 2 insertelements, 1 vector sub and, actually, one shuffle (2currently), to 2 scalar subs and 8 insertelements (2 broadcasts). Is this really so cost effective?

[vporpo]

test/Transforms/SLPVectorizer/X86/broadcast.ll

18–28

I am not sure what you mean. The cost of 2 insert elements + one 2-wide sub should be the same as the 2 scalar subs, so nothing to gain from the old code so far. Next, in the old code we have one shuffle for the left input to the 4-wide add and another shuffle for the right input. This is more expensive than the 2 broadcasts we have in the new code, because broadcasts are cheaper than shuffles.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

923

The function can be made const, I think.

924

auto->bool

931

auto &->const OperandData &

932

What if the Data.V is Undef? I think, we can use broadcast in this case too.

test/Transforms/SLPVectorizer/X86/broadcast.ll

18–28

Ah, yes, I see, you're right.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

923

It is modifying the 'IsUsed' so that we skip the operands that have already been identified as a broadcast, so it needs to call the non-const getData(), therefore it cannot be const.

932

Hmm, currently there is no restriction on Undefs, as Data.V can be any value. But maybe undefs should be matched with a lower priority ?

[vporpo]

Addressed the review comments.

[RKSimon]

@ABataev @dtemirbulatov any more comments?

[dtemirbulatov]

looks good to me.

[dtemirbulatov]

LGTM.

[vporpo]

Thank you for the reviews. Please commit it if @ABataev is also happy with it.

lib/Transforms/Vectorize/SLPVectorizer.cpp

class VLOperands {
     }
 
     /// \returns true if the data structure is empty.
     bool empty() const { return OpsVec.empty(); }
 
     /// Clears the data.
     void clear() { OpsVec.clear(); }
 
+    /// \Returns true if there are enough operands identical to \p Op to fill
+    /// the whole vector.
+    /// Note: This modifies the 'IsUsed' flag, so a cleanUsed() must follow.
+    bool shouldBroadcast(Value *Op, unsigned OpIdx, unsigned Lane) {
+      bool OpAPO = getData(OpIdx, Lane).APO;
+      for (unsigned Ln = 0, Lns = getNumLanes(); Ln != Lns; ++Ln) {
+        if (Ln == Lane)
+          continue;
+        // This is set to true if we found a candidate for broadcast at Lane.
+        bool FoundCandidate = false;
+        for (unsigned OpI = 0, OpE = getNumOperands(); OpI != OpE; ++OpI) {
+          OperandData &Data = getData(OpI, Ln);
+          if (Data.APO != OpAPO || Data.IsUsed)
+            continue;
+          if (Data.V == Op) {
+            FoundCandidate = true;
+            Data.IsUsed = true;
+            break;
+          }
+        }
+        if (!FoundCandidate)
+          return false;
+      }
+      return true;
+    }
+
   public:
     /// Initialize with all the operands of the instruction vector \p RootVL.
     VLOperands(ArrayRef<Value *> RootVL, const DataLayout &DL,
                ScalarEvolution &SE)
         : DL(DL), SE(SE) {
       // Append all the operands of RootVL.
       appendOperandsOfVL(RootVL);
     }
void reorder() {
 
       // Initialize the modes.
       for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
         Value *OpLane0 = getValue(OpIdx, FirstLane);
         // Keep track if we have instructions with all the same opcode on one
         // side.
         if (isa<LoadInst>(OpLane0))
           ReorderingModes[OpIdx] = ReorderingMode::Load;
-        else if (isa<Instruction>(OpLane0))
+        else if (isa<Instruction>(OpLane0)) {
+          // Check if OpLane0 should be broadcast.
+          if (shouldBroadcast(OpLane0, OpIdx, FirstLane))
+            ReorderingModes[OpIdx] = ReorderingMode::Splat;
+          else
             ReorderingModes[OpIdx] = ReorderingMode::Opcode;
+        }
         else if (isa<Constant>(OpLane0))
           ReorderingModes[OpIdx] = ReorderingMode::Constant;
         else if (isa<Argument>(OpLane0))
           // Our best hope is a Splat. It may save some cost in some cases.
           ReorderingModes[OpIdx] = ReorderingMode::Splat;
         else
           // NOTE: This should be unreachable.
           ReorderingModes[OpIdx] = ReorderingMode::Failed;
       }
 
       // If the initial strategy fails for any of the operand indexes, then we
       // perform reordering again in a second pass. This helps avoid assigning
       // high priority to the failed strategy, and should improve reordering for
       // the non-failed operand indexes.
       for (int Pass = 0; Pass != 2; ++Pass) {
         // Skip the second pass if the first pass did not fail.
         bool StrategyFailed = false;
-        // Mark the operand data as free to use for all but the first pass.
-        if (Pass > 0)
-          clearUsed();
+        // Mark all operand data as free to use.
         // We keep the original operand order for the FirstLane, so reorder the
         // rest of the lanes. We are visiting the nodes in a circular fashion,
         // using FirstLane as the center point and increasing the radius
         // distance.
         for (unsigned Distance = 1; Distance != NumLanes; ++Distance) {
           // Visit the lane on the right and then the lane on the left.
           for (int Direction : {+1, -1}) {
             int Lane = FirstLane + Direction * Distance;

test/Transforms/SLPVectorizer/X86/broadcast.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux -mcpu=corei7-avx -slp-threshold=-999 < %s | FileCheck %s
 
 
 ; S[0] = %v1 + %v2
 ; S[1] = %v2 + %v1
 ; S[2] = %v2 + %v1
 ; S[3] = %v1 + %v2
 ;
-; TODO: We should broadcast %v1 and %v2
+; We broadcast %v1 and %v2
 ;
+
 define void @bcast_vals(i64 *%A, i64 *%B, i64 *%S) {
 ; CHECK-LABEL: @bcast_vals(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A0:%.*]] = load i64, i64* [[A:%.*]], align 8
 ; CHECK-NEXT:    [[B0:%.*]] = load i64, i64* [[B:%.*]], align 8
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x i64> undef, i64 [[A0]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x i64> [[TMP0]], i64 [[B0]], i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = sub <2 x i64> [[TMP1]], <i64 1, i64 1>
-; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i64> [[TMP2]], <2 x i64> undef, <4 x i32> <i32 0, i32 1, i32 1, i32 0>
-; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i64> [[SHUFFLE]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x i64> undef, i64 [[TMP3]], i32 0
-; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <4 x i64> [[SHUFFLE]], i32 0
-; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <2 x i64> [[TMP4]], i64 [[TMP5]], i32 1
-; CHECK-NEXT:    [[SHUFFLE1:%.*]] = shufflevector <2 x i64> [[TMP6]], <2 x i64> undef, <4 x i32> <i32 0, i32 1, i32 1, i32 0>
-; CHECK-NEXT:    [[TMP7:%.*]] = add <4 x i64> [[SHUFFLE]], [[SHUFFLE1]]
+; CHECK-NEXT:    [[V1:%.*]] = sub i64 [[A0]], 1
+; CHECK-NEXT:    [[V2:%.*]] = sub i64 [[B0]], 1
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <4 x i64> undef, i64 [[V1]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x i64> [[TMP0]], i64 [[V1]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i64> [[TMP1]], i64 [[V1]], i32 2
+; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i64> [[TMP2]], i64 [[V1]], i32 3
+; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i64> undef, i64 [[V2]], i32 0
+; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i64> [[TMP4]], i64 [[V2]], i32 1
+; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i64> [[TMP5]], i64 [[V2]], i32 2
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i64> [[TMP6]], i64 [[V2]], i32 3
+; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i64> [[TMP3]], [[TMP7]]
 ; CHECK-NEXT:    [[IDXS0:%.*]] = getelementptr inbounds i64, i64* [[S:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXS1:%.*]] = getelementptr inbounds i64, i64* [[S]], i64 1
 ; CHECK-NEXT:    [[IDXS2:%.*]] = getelementptr inbounds i64, i64* [[S]], i64 2
 ; CHECK-NEXT:    [[IDXS3:%.*]] = getelementptr inbounds i64, i64* [[S]], i64 3
-; CHECK-NEXT:    [[TMP8:%.*]] = bitcast i64* [[IDXS0]] to <4 x i64>*
-; CHECK-NEXT:    store <4 x i64> [[TMP7]], <4 x i64>* [[TMP8]], align 8
+; CHECK-NEXT:    [[TMP9:%.*]] = bitcast i64* [[IDXS0]] to <4 x i64>*
+; CHECK-NEXT:    store <4 x i64> [[TMP8]], <4 x i64>* [[TMP9]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %A0 = load i64, i64 *%A, align 8
   %B0 = load i64, i64 *%B, align 8
 
   %v1 = sub i64 %A0, 1
   %v2 = sub i64 %B0, 1
entry:
   ret void
 }
 
 ; S[0] = %v1 + %v2
 ; S[1] = %v3 + %v1
 ; S[2] = %v5 + %v1
 ; S[3] = %v1 + %v4
 ;
-; TODO: We should broadcast %v1.
+; We broadcast %v1.
+
 ;
 define void @bcast_vals2(i16 *%A, i16 *%B, i16 *%C, i16 *%D, i16 *%E, i32 *%S) {
 ; CHECK-LABEL: @bcast_vals2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A0:%.*]] = load i16, i16* [[A:%.*]], align 8
 ; CHECK-NEXT:    [[B0:%.*]] = load i16, i16* [[B:%.*]], align 8
 ; CHECK-NEXT:    [[C0:%.*]] = load i16, i16* [[C:%.*]], align 8
 ; CHECK-NEXT:    [[D0:%.*]] = load i16, i16* [[D:%.*]], align 8
 ; CHECK-NEXT:    [[E0:%.*]] = load i16, i16* [[E:%.*]], align 8
 ; CHECK-NEXT:    [[V1:%.*]] = sext i16 [[A0]] to i32
-; CHECK-NEXT:    [[V2:%.*]] = sext i16 [[B0]] to i32
-; CHECK-NEXT:    [[V3:%.*]] = sext i16 [[C0]] to i32
-; CHECK-NEXT:    [[V4:%.*]] = sext i16 [[D0]] to i32
-; CHECK-NEXT:    [[V5:%.*]] = sext i16 [[E0]] to i32
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <4 x i32> undef, i32 [[V1]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x i32> [[TMP0]], i32 [[V3]], i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i32> [[TMP1]], i32 [[V5]], i32 2
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> [[TMP2]], i32 [[V1]], i32 3
-; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i32> undef, i32 [[V2]], i32 0
-; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> [[TMP4]], i32 [[V1]], i32 1
-; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i32> [[TMP5]], i32 [[V1]], i32 2
-; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i32> [[TMP6]], i32 [[V4]], i32 3
-; CHECK-NEXT:    [[TMP8:%.*]] = add <4 x i32> [[TMP3]], [[TMP7]]
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <4 x i16> undef, i16 [[B0]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <4 x i16> [[TMP0]], i16 [[C0]], i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i16> [[TMP1]], i16 [[E0]], i32 2
+; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i16> [[TMP2]], i16 [[D0]], i32 3
+; CHECK-NEXT:    [[TMP4:%.*]] = sext <4 x i16> [[TMP3]] to <4 x i32>
+; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> undef, i32 [[V1]], i32 0
+; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i32> [[TMP5]], i32 [[V1]], i32 1
+; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <4 x i32> [[TMP6]], i32 [[V1]], i32 2
+; CHECK-NEXT:    [[TMP8:%.*]] = insertelement <4 x i32> [[TMP7]], i32 [[V1]], i32 3
+; CHECK-NEXT:    [[TMP9:%.*]] = add <4 x i32> [[TMP8]], [[TMP4]]
 ; CHECK-NEXT:    [[IDXS0:%.*]] = getelementptr inbounds i32, i32* [[S:%.*]], i64 0
 ; CHECK-NEXT:    [[IDXS1:%.*]] = getelementptr inbounds i32, i32* [[S]], i64 1
 ; CHECK-NEXT:    [[IDXS2:%.*]] = getelementptr inbounds i32, i32* [[S]], i64 2
 ; CHECK-NEXT:    [[IDXS3:%.*]] = getelementptr inbounds i32, i32* [[S]], i64 3
-; CHECK-NEXT:    [[TMP9:%.*]] = bitcast i32* [[IDXS0]] to <4 x i32>*
-; CHECK-NEXT:    store <4 x i32> [[TMP8]], <4 x i32>* [[TMP9]], align 8
+; CHECK-NEXT:    [[TMP10:%.*]] = bitcast i32* [[IDXS0]] to <4 x i32>*
+; CHECK-NEXT:    store <4 x i32> [[TMP9]], <4 x i32>* [[TMP10]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %A0 = load i16, i16 *%A, align 8
   %B0 = load i16, i16 *%B, align 8
   %C0 = load i16, i16 *%C, align 8
   %D0 = load i16, i16 *%D, align 8
   %E0 = load i16, i16 *%E, align 8