[SLP] Steer for the best chance in tryToVectorize() when rooting with binary ops.

[vdmitrie]

Summary

tryToVectorize() method implements one of searching paths for vectorizable tree roots in SLP vectorizer,
specifically for binary and comparison operations. Order of making probes for various scalar pairs
was defined by its implementation: the instruction operands, then climb over one operand if
the instruction is its sole user and then perform same actions for another operand if previous
attempts failed. Problem with this approach is that among these options we can have more than a
single vectorizable tree candidate and it is not necessarily the one which encountered first.
Trying to build vectorizable tree for each possible combination for just evaluation is expensive.
But we already have lookahead heuristics mechanism which we use for finding best pick among
operands of commutative instructions. It calculates cumulative score for candidates in two
consecutive lanes. This patch introduces use of the heuristics for choosing the best pair among
several combinations. We only try one that looks as most promising for vectorization.
Additional benefit is that we reduce total number of vectorization trees built for probes
because we skip those looking non-profitable early.

[ABataev]

Hi Valery, thanks for the patch. This looks good! Could you split it into 2 patches: one that renames lookahead heuristics (NFC) and the second (functional) one?

llvm/test/Transforms/SLPVectorizer/AArch64/invalid_type.ll

7

Do you need to update this test?

[vdmitrie]

In D124309#3469277, @ABataev wrote:

Hi Valery, thanks for the patch. This looks good! Could you split it into 2 patches: one that renames lookahead heuristics (NFC) and the second (functional) one?

Hi Alexey,
yeah, will do that. I actually have it split locally exactly like you suggested.

[vdmitrie]

llvm/test/Transforms/SLPVectorizer/AArch64/invalid_type.ll

7

I added check for vector types at line 9176 so we now are not reaching emission of the remark.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1046–1047

nit: It also holds the operands of a VL, so it is probably best to mention this here too.

2016

nit: perhaps findBestRootPair ?

2018

We could also have a separate max-depth limit for this, because I guess it will not ran as frequently as the other one, so we could have a higher depth if required.

9227

nit: I think we can drop .hasValue(), if (!BestCandidate) should work fine.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1046–1047

Hm, I'm not sure I understand what you mean here. You might be mislead by the way diff is shown here.
This is not renaming of existing VLOperands.
This new helper class formed basically by couple routines: getShallowScore and getScoreAtLevelRec which were pulled out of VLOperands along with score constants. The class does not store anything from VL.
It only needs total number of lanes for scoring. I even changed both methods to be const.

2016

Thanks for suggestion. Will apply it with next rebase.

2018

Will do. Any suggestion about option name?

9227

sure

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

1046–1047

Oops, yeah you are right, I got confused by the diff, sorry about that.
Nice, thanks for refactoring it, it looks much better this way :D

2018

Hmm if we are sticking to using root to describe this, perhaps RootLookAheadMaxDpeth?

[vdmitrie]

https://reviews.llvm.org/D124313 is the NFC split.

[vdmitrie]

rebased + applied suggestions

[ABataev]

LG

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

static cl::opt<unsigned> MinTreeSize(
     cl::desc("Only vectorize small trees if they are fully vectorizable"));
 
 // The maximum depth that the look-ahead score heuristic will explore.
 // The higher this value, the higher the compilation time overhead.
 static cl::opt<int> LookAheadMaxDepth(
     "slp-max-look-ahead-depth", cl::init(2), cl::Hidden,
     cl::desc("The maximum look-ahead depth for operand reordering scores"));
 
+// The maximum depth that the look-ahead score heuristic will explore
+// when it probing among candidates for vectorization tree roots.
+// The higher this value, the higher the compilation time overhead but unlike
+// similar limit for operands ordering this is less frequently used, hence
+// impact of higher value is less noticeable.
+static cl::opt<int> RootLookAheadMaxDepth(
+    "slp-max-root-look-ahead-depth", cl::init(2), cl::Hidden,
+    cl::desc("The maximum look-ahead depth for searching best rooting option"));
+
 static cl::opt<bool>
     ViewSLPTree("view-slp-tree", cl::Hidden,
                 cl::desc("Display the SLP trees with Graphviz"));
 
 // Limit the number of alias checks. The limit is chosen so that
 // it has no negative effect on the llvm benchmarks.
 static const unsigned AliasedCheckLimit = 10;
 
#ifndef NDEBUG
     void dump(raw_ostream &OS) const {
       OS << "{User:" << (UserTE ? std::to_string(UserTE->Idx) : "null")
          << " EdgeIdx:" << EdgeIdx << "}";
     }
     LLVM_DUMP_METHOD void dump() const { dump(dbgs()); }
 #endif
   };
 
   /// A helper class used for scoring candidates for two consecutive lanes.
   class LookAheadHeuristics {
     const DataLayout &DL;
     ScalarEvolution &SE;
     const BoUpSLP &R;
     int NumLanes; // Total number of lanes (aka vectorization factor).
     int MaxLevel; // The maximum recursion depth for accumulating score.
 
   public:
     LookAheadHeuristics(const DataLayout &DL, ScalarEvolution &SE,
LLVM_DUMP_METHOD raw_ostream &print(raw_ostream &OS) const {
       return OS;
     }
 
     /// Debug print.
     LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
 #endif
   };
 
+  /// Evaluate each pair in \p Candidates and return index into \p Candidates
+  /// for a pair which have highest score deemed to have best chance to form
+  /// root of profitable tree to vectorize. Return None if no candidate scored
+  /// above the LookAheadHeuristics::ScoreFail.
+  Optional<int>
+  findBestRootPair(ArrayRef<std::pair<Value *, Value *>> Candidates) {
+    LookAheadHeuristics LookAhead(*DL, *SE, *this, /*NumLanes=*/2,
+                                  RootLookAheadMaxDepth);
+    int BestScore = LookAheadHeuristics::ScoreFail;
+    Optional<int> Index = None;
+    for (int I : seq<int>(0, Candidates.size())) {
+      int Score = LookAhead.getScoreAtLevelRec(Candidates[I].first,
+                                               Candidates[I].second,
+                                               /*U1=*/nullptr, /*U2=*/nullptr,
+                                               /*Level=*/1, None);
+      if (Score > BestScore) {
+        BestScore = Score;
+        Index = I;
+      }
+    }
+    return Index;
+  }
+
   /// Checks if the instruction is marked for deletion.
   bool isDeleted(Instruction *I) const { return DeletedInstructions.count(I); }
 
   /// Removes an instruction from its block and eventually deletes it.
   /// It's like Instruction::eraseFromParent() except that the actual deletion
   /// is delayed until BoUpSLP is destructed.
   void eraseInstruction(Instruction *I) {
     DeletedInstructions.insert(I);
bool SLPVectorizerPass::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
   }
   return Changed;
 }
 
 bool SLPVectorizerPass::tryToVectorize(Instruction *I, BoUpSLP &R) {
   if (!I)
     return false;
 
-  if (!isa<BinaryOperator>(I) && !isa<CmpInst>(I))
+  if ((!isa<BinaryOperator>(I) && !isa<CmpInst>(I)) ||
+      isa<VectorType>(I->getType()))
     return false;
 
   Value *P = I->getParent();
 
   // Vectorize in current basic block only.
   auto *Op0 = dyn_cast<Instruction>(I->getOperand(0));
   auto *Op1 = dyn_cast<Instruction>(I->getOperand(1));
   if (!Op0 || !Op1 || Op0->getParent() != P || Op1->getParent() != P)
     return false;
 
-  // Try to vectorize V.
-  if (tryToVectorizePair(Op0, Op1, R))
-    return true;
+  // First collect all possible candidates
+  SmallVector<std::pair<Value *, Value *>, 4> Candidates;
+  Candidates.emplace_back(Op0, Op1);
 
   auto *A = dyn_cast<BinaryOperator>(Op0);
   auto *B = dyn_cast<BinaryOperator>(Op1);
   // Try to skip B.
-  if (B && B->hasOneUse()) {
+  if (A && B && B->hasOneUse()) {
     auto *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
     auto *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
-    if (B0 && B0->getParent() == P && tryToVectorizePair(A, B0, R))
-      return true;
-    if (B1 && B1->getParent() == P && tryToVectorizePair(A, B1, R))
-      return true;
+    if (B0 && B0->getParent() == P)
+      Candidates.emplace_back(A, B0);
+    if (B1 && B1->getParent() == P)
+      Candidates.emplace_back(A, B1);
   }
-
   // Try to skip A.
-  if (A && A->hasOneUse()) {
+  if (B && A && A->hasOneUse()) {
     auto *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
     auto *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
-    if (A0 && A0->getParent() == P && tryToVectorizePair(A0, B, R))
-      return true;
-    if (A1 && A1->getParent() == P && tryToVectorizePair(A1, B, R))
-      return true;
+    if (A0 && A0->getParent() == P)
+      Candidates.emplace_back(A0, B);
+    if (A1 && A1->getParent() == P)
+      Candidates.emplace_back(A1, B);
   }
+
+  if (Candidates.size() == 1)
+    return tryToVectorizePair(Op0, Op1, R);
+
+  // We have multiple options. Try to pick the single best.
+  Optional<int> BestCandidate = R.findBestRootPair(Candidates);
+  if (!BestCandidate)
     return false;
+  return tryToVectorizePair(Candidates[*BestCandidate].first,
+                            Candidates[*BestCandidate].second, R);
 }
 
 namespace {
 
 /// Model horizontal reductions.
 ///
 /// A horizontal reduction is a tree of reduction instructions that has values
 /// that can be put into a vector as its leaves. For example:

llvm/test/Transforms/SLPVectorizer/AArch64/invalid_type.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -slp-vectorizer -S -pass-remarks-missed=slp-vectorizer 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64-unknown-linux-gnu"
 
 ; This test check that slp vectorizer is not trying to vectorize instructions already vectorized.
-; CHECK: remark: <unknown>:0:0: Cannot SLP vectorize list: type <16 x i8> is unsupported by vectorizer
 
 define void @vector() {
+; CHECK-LABEL: @vector(
+; CHECK-NEXT:    [[LOAD0:%.*]] = tail call <16 x i8> @vector.load(<16 x i8>* undef, i32 1)
+; CHECK-NEXT:    [[LOAD1:%.*]] = tail call <16 x i8> @vector.load(<16 x i8>* undef, i32 2)
+; CHECK-NEXT:    [[ADD:%.*]] = add <16 x i8> [[LOAD1]], [[LOAD0]]
+; CHECK-NEXT:    tail call void @vector.store(<16 x i8> [[ADD]], <16 x i8>* undef, i32 1)
+; CHECK-NEXT:    ret void
+;
   %load0 = tail call <16 x i8> @vector.load(<16 x i8> *undef, i32 1)
   %load1 = tail call <16 x i8> @vector.load(<16 x i8> *undef, i32 2)
   %add = add <16 x i8> %load1, %load0
   tail call void @vector.store(<16 x i8> %add, <16 x i8>* undef, i32 1)
   ret void
 }
 
 declare <16 x i8> @vector.load(<16 x i8>*, i32)
 declare void @vector.store(<16 x i8>, <16 x i8>*, i32)

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector-inseltpoison.ll

 ; MINTREESIZE-NEXT:    [[Q3:%.*]] = extractelement <4 x float> [[RD]], i32 3
 ; MINTREESIZE-NEXT:    [[TMP7:%.*]] = insertelement <2 x float> poison, float [[Q2]], i32 0
 ; MINTREESIZE-NEXT:    [[TMP8:%.*]] = insertelement <2 x float> [[TMP7]], float [[Q3]], i32 1
 ; MINTREESIZE-NEXT:    [[Q4:%.*]] = fadd float [[Q0]], [[Q1]]
 ; MINTREESIZE-NEXT:    [[Q5:%.*]] = fadd float [[Q2]], [[Q3]]
 ; MINTREESIZE-NEXT:    [[TMP9:%.*]] = insertelement <2 x float> poison, float [[Q4]], i32 0
 ; MINTREESIZE-NEXT:    [[TMP10:%.*]] = insertelement <2 x float> [[TMP9]], float [[Q5]], i32 1
 ; MINTREESIZE-NEXT:    [[Q6:%.*]] = fadd float [[Q4]], [[Q5]]
-; MINTREESIZE-NEXT:    [[TMP11:%.*]] = insertelement <2 x float> poison, float [[Q6]], i32 0
-; MINTREESIZE-NEXT:    [[TMP12:%.*]] = insertelement <2 x float> [[TMP11]], float [[Q5]], i32 1
 ; MINTREESIZE-NEXT:    [[QI:%.*]] = fcmp olt float [[Q6]], [[Q5]]
 ; MINTREESIZE-NEXT:    call void @llvm.assume(i1 [[QI]])
 ; MINTREESIZE-NEXT:    ret <4 x float> undef
 ;
   %c0 = extractelement <4 x i32> %c, i32 0
   %c1 = extractelement <4 x i32> %c, i32 1
   %c2 = extractelement <4 x i32> %c, i32 2
   %c3 = extractelement <4 x i32> %c, i32 3

llvm/test/Transforms/SLPVectorizer/X86/insert-element-build-vector.ll

 ; MINTREESIZE-NEXT:    [[Q3:%.*]] = extractelement <4 x float> [[RD]], i32 3
 ; MINTREESIZE-NEXT:    [[TMP7:%.*]] = insertelement <2 x float> poison, float [[Q2]], i32 0
 ; MINTREESIZE-NEXT:    [[TMP8:%.*]] = insertelement <2 x float> [[TMP7]], float [[Q3]], i32 1
 ; MINTREESIZE-NEXT:    [[Q4:%.*]] = fadd float [[Q0]], [[Q1]]
 ; MINTREESIZE-NEXT:    [[Q5:%.*]] = fadd float [[Q2]], [[Q3]]
 ; MINTREESIZE-NEXT:    [[TMP9:%.*]] = insertelement <2 x float> poison, float [[Q4]], i32 0
 ; MINTREESIZE-NEXT:    [[TMP10:%.*]] = insertelement <2 x float> [[TMP9]], float [[Q5]], i32 1
 ; MINTREESIZE-NEXT:    [[Q6:%.*]] = fadd float [[Q4]], [[Q5]]
-; MINTREESIZE-NEXT:    [[TMP11:%.*]] = insertelement <2 x float> poison, float [[Q6]], i32 0
-; MINTREESIZE-NEXT:    [[TMP12:%.*]] = insertelement <2 x float> [[TMP11]], float [[Q5]], i32 1
 ; MINTREESIZE-NEXT:    [[QI:%.*]] = fcmp olt float [[Q6]], [[Q5]]
 ; MINTREESIZE-NEXT:    call void @llvm.assume(i1 [[QI]])
 ; MINTREESIZE-NEXT:    ret <4 x float> undef
 ;
   %c0 = extractelement <4 x i32> %c, i32 0
   %c1 = extractelement <4 x i32> %c, i32 1
   %c2 = extractelement <4 x i32> %c, i32 2
   %c3 = extractelement <4 x i32> %c, i32 3

llvm/test/Transforms/SLPVectorizer/X86/vectorize-pair-path.ll

 ; encountered first (like here).
 
 define double @root_selection(double %a, double %b, double %c, double %d) local_unnamed_addr #0 {
 ; CHECK-LABEL: @root_selection(
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> poison, double [[A:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> [[TMP1]], double [[B:%.*]], i32 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = fdiv fast <2 x double> [[TMP2]], <double 7.000000e+00, double 5.000000e+00>
 ; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <2 x double> [[TMP3]], i32 1
-; CHECK-NEXT:    [[I11:%.*]] = fmul fast double [[TMP4]], undef
+; CHECK-NEXT:    [[I09:%.*]] = fmul fast double [[TMP4]], undef
+; CHECK-NEXT:    [[I10:%.*]] = fsub fast double undef, [[I09]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = fmul fast <2 x double> [[TMP3]], <double 3.000000e+00, double undef>
-; CHECK-NEXT:    [[TMP6:%.*]] = fmul fast <2 x double> undef, [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = fsub fast <2 x double> undef, [[TMP5]]
-; CHECK-NEXT:    [[TMP8:%.*]] = shufflevector <2 x double> [[TMP6]], <2 x double> [[TMP7]], <2 x i32> <i32 0, i32 3>
-; CHECK-NEXT:    [[TMP9:%.*]] = insertelement <2 x double> <double undef, double poison>, double [[I11]], i32 1
-; CHECK-NEXT:    [[TMP10:%.*]] = fsub fast <2 x double> [[TMP8]], [[TMP9]]
-; CHECK-NEXT:    [[TMP11:%.*]] = fmul fast <2 x double> [[TMP8]], [[TMP9]]
-; CHECK-NEXT:    [[TMP12:%.*]] = shufflevector <2 x double> [[TMP10]], <2 x double> [[TMP11]], <2 x i32> <i32 0, i32 3>
-; CHECK-NEXT:    [[TMP13:%.*]] = fmul fast <2 x double> [[TMP12]], <double 4.000000e+00, double 1.100000e+01>
-; CHECK-NEXT:    [[TMP14:%.*]] = fsub fast <2 x double> [[TMP12]], <double 4.000000e+00, double 1.100000e+01>
-; CHECK-NEXT:    [[TMP15:%.*]] = shufflevector <2 x double> [[TMP13]], <2 x double> [[TMP14]], <2 x i32> <i32 0, i32 3>
-; CHECK-NEXT:    [[TMP16:%.*]] = fdiv fast <2 x double> [[TMP15]], <double 1.400000e+00, double 1.200000e+01>
-; CHECK-NEXT:    [[TMP17:%.*]] = fmul fast <2 x double> [[TMP15]], <double 1.400000e+00, double 1.200000e+01>
-; CHECK-NEXT:    [[TMP18:%.*]] = shufflevector <2 x double> [[TMP16]], <2 x double> [[TMP17]], <2 x i32> <i32 0, i32 3>
-; CHECK-NEXT:    [[TMP19:%.*]] = fadd fast <2 x double> [[TMP18]], <double undef, double 1.400000e+00>
-; CHECK-NEXT:    [[TMP20:%.*]] = fdiv fast <2 x double> [[TMP18]], <double undef, double 1.400000e+00>
-; CHECK-NEXT:    [[TMP21:%.*]] = shufflevector <2 x double> [[TMP19]], <2 x double> [[TMP20]], <2 x i32> <i32 0, i32 3>
-; CHECK-NEXT:    [[TMP22:%.*]] = extractelement <2 x double> [[TMP21]], i32 0
-; CHECK-NEXT:    [[TMP23:%.*]] = extractelement <2 x double> [[TMP21]], i32 1
-; CHECK-NEXT:    [[I16:%.*]] = fadd fast double [[TMP22]], [[TMP23]]
+; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <2 x double> <double undef, double poison>, double [[I10]], i32 1
+; CHECK-NEXT:    [[TMP7:%.*]] = fmul fast <2 x double> [[TMP6]], [[TMP5]]
+; CHECK-NEXT:    [[TMP8:%.*]] = fsub fast <2 x double> [[TMP7]], <double undef, double 1.100000e+01>
+; CHECK-NEXT:    [[TMP9:%.*]] = fmul fast <2 x double> [[TMP8]], <double 4.000000e+00, double 1.200000e+01>
+; CHECK-NEXT:    [[TMP10:%.*]] = fdiv fast <2 x double> [[TMP9]], <double 1.400000e+00, double 1.400000e+00>
+; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <2 x double> [[TMP10]], i32 0
+; CHECK-NEXT:    [[I07:%.*]] = fadd fast double undef, [[TMP11]]
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <2 x double> [[TMP10]], i32 1
+; CHECK-NEXT:    [[I16:%.*]] = fadd fast double [[I07]], [[TMP12]]
 ; CHECK-NEXT:    [[I17:%.*]] = fadd fast double [[I16]], [[C:%.*]]
 ; CHECK-NEXT:    [[I18:%.*]] = fadd fast double [[I17]], [[D:%.*]]
 ; CHECK-NEXT:    ret double [[I18]]
 ;
   %i01 = fdiv fast double %a, 7.0
   %i02 = fmul fast double %i01, 3.0
   %i03 = fmul fast double undef, %i02
   %i04 = fsub fast double %i03, undef