[SLP] Improve root steering by building actual trees instead of calling the look-ahead heuristic

[vporpo]

Summary

Finding the best roots using the lookahead heuristic is not as accurate as
building short trees and comparing their cost.

[vporpo]

This fixes a regression in SingleSource/Benchmarks/Misc/flops-5.c. Increasing the RootLookaheadMaxDepth doesn't fix the issue either. Building small trees instead of calling the lookahead heuristic seems to be more accurate in this case.

[vporpo]

Updated checks in tests.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

I'm afraid of increasing compile time. All this stuff includes scheduling, which may take lots of time for large basic blocks.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

What if we set a flag to disable scheduling for these types of fast tree estimations?

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Yep, I agree. this will be more expensive for compile time.
What about combining both worlds? I mean first try to use lookahead heuristics to get the single best. And if we can't narrow down to just one pair only then switch into probing via building trees.
I believe it will not happen too frequently. We can also increase lookahead depth to make it even less frequent when we need to build vectorizable tree.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

There is a problem with this fix that it tries to avoid/mask the problem, not fix it. The fact that LookAhead.getScoreAtLevelRec does not work here means that we're doing something wrong there or missing something. Would be good to try to improve LookAhead.getScoreAtLevelRec

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

This problem does actually not have a perfect solution. This is a heuristics and it will always have something missed.
You can improve it to fix one particular case but there will be eventually another instance of the same problem.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Yes, sure. But if the heuristic misses something, better to try tweak the heuristic rather than using actual cost/vectorization attempt and just ignore the heuristic, which exists exactly for this purpose.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

No, " just ignore" is not what I said. We definitely should use the heuristics. But when it happens that we came to its limits then we could use more fine grained tools.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

I rather doubt that building a graph can be called a "fine grained tool". This is different tool, not intended for the analysis. We can extract some functionality out of there (to a separate function/member function) and make the heuristic more smart, but not use the build graph directly.
Same problem with the heuristic may exist in some other places, we need to handle them too.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Cost modeling is the tool I referred to as a "fine grained tool". We have to build a graph to run it. So it's sort of necessary evil. In this sense trying to turn off scheduler for the purpose of using CM as finer grained heuristics does not sound like a crazy idea.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

That's what I don't agree here. Cost model is not the tool for the modelling. For modelling we have heuristic. If it is not good, need to tweak it.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

One issue with the lookahead search is that it is trying both sides of commutative operations, so this doesn't scale if we need to increase the depth. So we need a different tool for testing deeper trees. I agree that there may be something that the lookahead heuristic is missing here, but I would argue that it is the wrong tool for the job. The buildTree() logic is a much more accurate for this. Reusing the existing buildTree logic with some compromises (e.g, limiting size and disabling scheduling) seems like a good compromise to me.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

I would oppose that. I would not use buildTree() for estimation. If there is a part, which can be used for better estimation, better to extract it to a separate function/class and the reuse it in the heuristic and actual graph building separately.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

What is the reasoning for opposing it?

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

That's what I don't agree here. Cost model is not the tool for the modelling. For modelling we have heuristic. If it is not good, need to tweak it.

It would be nice if you explained why you are against using CM for selecting a candidate.
Cost model as its name suggests is supposed to be used for modeling.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Bad design decision. We have 4 stages.

1. Analysis.
2. Tree building.
3. Cost estimation.
4. Codegen.

You want to make a circular dependence between Analysis and Tree building/Cost estimation.

But I'm not against reusing some of the code from buildTree()/cost estimation for the analysis phase. I'm just saying that this functionality must be extracted and then reused for the analysis and for the tree building/cost estimation (if possible, to reduce maintenance burden).

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Because it is not modelling, it is analysis

2044–2050

I mean, you want to use it not for modelling but for the analysis

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

I think the high level design that you showed is not very accurate. We are actually doing multiple "tree builds" and "cost estimations" before generating code even in the current design. I don't see the "circular dependency" issue being introduced by this.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Distinction between the two is moot.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

Thta's not because we mix analysis/modelling/estimation, but just because cost estimation shows that the tree is not profitable. The question is not about number of attempts, it is about the design.

2044–2050

Weak argument.

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

What about alternative solution which is kind of step back but buildTree+CM is not used for analysis?

if lookahead heuristics cannot find single best findBestRootPair returns all indices that give the maximum score. Caller then uses approach it used before: tries to vectorize each until it finds the first which is profitable.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

I don't see any strong argument against using buildTree+CostModel as long as buildTree is fast enough. The argument that this is somehow changing the design makes little sense because the pass is already following this buildTree+CostModel design. The only exception is perhaps for the lookahead search which is actually an example of a design to avoid: it is using its own custom tree-building and cost modeling, and requires special maintenance.

Also the argument that we should extract some of the functionality and place it in a separate component is not very strong. Replicating similar functionality in multiple places is something that a good design should avoid. It just increases the maintenance overhead and will inevitably lead to divergence.

[ABataev]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

What about alternative solution which is kind of step back but buildTree+CM is not used for analysis?

if lookahead heuristics cannot find single best findBestRootPair returns all indices that give the maximum score. Caller then uses approach it used before: tries to vectorize each until it finds the first which is profitable.

Yes, it may work as a quick solution.

[vporpo]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

2044–2050

if lookahead heuristics cannot find single best findBestRootPair returns all indices that give the maximum score. Caller then uses approach it used before: tries to vectorize each until it finds the first which is profitable.

That won't work because lookahead finds a single best, but it turns out to be the wrong one.

[vporpo]

Disabled the scheduler for the fast buildtree.

I checked the compile time overhead with perf on the lit test, and it is about the same as the version before @vdmitrie's patch 88b9e46fb54c.

[vporpo]

I think that providing a buildTreeFastAndGetCost() style of function is a decent solution for these types of problems, but I guess this needs more discussion. Adding @RKSimon and @dmgreen .

[vdmitrie]

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

849

(If we finally agree with taking this path)
It should probably be possible to introduce simulation mode to BlockScheduling rather than guard each BS interface call.

905

this description update is seems leftover from the previous diff (i.e. not intentional)

[vporpo]

Fixed stale comment and added DisableScheduling flag to BlockScheduling.

[vporpo]

ping

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"));
+// The maximum tree size that will use when 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<unsigned> RootLookAheadMaxSize(
+    "slp-root-look-ahead-max-size", cl::init(5), cl::Hidden,
+    cl::desc("The maximum tree size 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;

 }
 
 namespace slpvectorizer {
 
 /// Bottom Up SLP Vectorizer.
 class BoUpSLP {
   struct TreeEntry;
   struct ScheduleData;
+  /// Limit the size of the SLP tree to this many nodes.
+  Optional<unsigned> MaxTreeSize;
+  /// Disables scheduling. This is to limit the compilation time used by
+  /// buildTree(), usually in combination with \p MaxTreeSize for quickly
+  /// building approximate trees that can be used for estimating which roots are
+  /// to be prefered.
+  /// WARNING: If this is enabled the tree is not guaranteed to contain valid
+  /// instruction bundles that can actually get codegened.
+  bool ForceDisableScheduling = false;
 
 public:
   using ValueList = SmallVector<Value *, 8>;
   using InstrList = SmallVector<Instruction *, 16>;
   using ValueSet = SmallPtrSet<Value *, 16>;
   using StoreList = SmallVector<StoreInst *, 8>;
   using ExtraValueToDebugLocsMap =
       MapVector<Value *, SmallVector<Instruction *, 2>>;
public:
   InstructionCost getSpillCost() const;
 
   /// \returns the vectorization cost of the subtree that starts at \p VL.
   /// A negative number means that this is profitable.
   InstructionCost getTreeCost(ArrayRef<Value *> VectorizedVals = None);
 
   /// Construct a vectorizable tree that starts at \p Roots, ignoring users for
   /// the purpose of scheduling and extraction in the \p UserIgnoreLst.
   void buildTree(ArrayRef<Value *> Roots,
                  ArrayRef<Value *> UserIgnoreLst = None);
 
+  /// Builds a tree starting from \p roots with up to \p MaxSize nodes. For
+  /// faster compilation time scheduling is disabled by default, or can be
+  /// enabled with \p DisableScheduling = false.
+  /// This function is to be used for a look-ahead style evaluation of root
+  /// nodes and estimating which ones are worth building a full tree for.
+  InstructionCost buildTreeFastAndGetCost(ArrayRef<Value *> Roots,
+                                          Optional<unsigned> MaxSize = 5,
+                                          bool DisableScheduling = true);
+
   /// Builds external uses of the vectorized scalars, i.e. the list of
   /// vectorized scalars to be extracted, their lanes and their scalar users. \p
   /// ExternallyUsedValues contains additional list of external uses to handle
   /// vectorization of reductions.
   void
   buildExternalUses(const ExtraValueToDebugLocsMap &ExternallyUsedValues = {});
 
   /// Clear the internal data structures that are created by 'buildTree'.
   void deleteTree() {
+    ForceDisableScheduling = false;
+    MaxTreeSize = None;
     VectorizableTree.clear();
     ScalarToTreeEntry.clear();
     MustGather.clear();
     ExternalUses.clear();
     for (auto &Iter : BlocksSchedules) {
       BlockScheduling *BS = Iter.second.get();
       BS->clear();
     }
#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;
+    InstructionCost BestCost = InstructionCost::getMax();
     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;
+      SmallVector<Value *, 2> Roots(
+          {Candidates[I].first, Candidates[I].second});
+      InstructionCost Cost =
+          buildTreeFastAndGetCost(Roots, RootLookAheadMaxSize.getValue());
+      if (Cost < BestCost) {
+        BestCost = Cost;
         Index = I;
       }
     }
     return Index;
   }
 
   /// Checks if the instruction is marked for deletion.
   bool isDeleted(Instruction *I) const { return DeletedInstructions.count(I); }
 
if (ReorderIndices.empty()) {
       Last->setOperations(S);
       Last->ReorderIndices.append(ReorderIndices.begin(), ReorderIndices.end());
     }
     if (Last->State != TreeEntry::NeedToGather) {
       for (Value *V : VL) {
         assert(!getTreeEntry(V) && "Scalar already in tree!");
         ScalarToTreeEntry[V] = Last;
       }
+      if (!ForceDisableScheduling) {
         // Update the scheduler bundle to point to this TreeEntry.
         ScheduleData *BundleMember = Bundle.getValue();
         assert((BundleMember || isa<PHINode>(S.MainOp) ||
                 isVectorLikeInstWithConstOps(S.MainOp) ||
                 doesNotNeedToSchedule(VL)) &&
                "Bundle and VL out of sync");
         if (BundleMember) {
           for (Value *V : VL) {
             if (doesNotNeedToBeScheduled(V))
               continue;
             assert(BundleMember && "Unexpected end of bundle.");
             BundleMember->TE = Last;
             BundleMember = BundleMember->NextInBundle;
           }
         }
         assert(!BundleMember && "Bundle and VL out of sync");
+      }
     } else {
       MustGather.insert(VL.begin(), VL.end());
     }
 
     if (UserTreeIdx.UserTE)
       Last->UserTreeIndices.push_back(UserTreeIdx);
 
     return Last;
struct BlockScheduling {
     bool isInSchedulingRegion(ScheduleData *SD) const {
       return SD->SchedulingRegionID == SchedulingRegionID;
     }
 
     /// Marks an instruction as scheduled and puts all dependent ready
     /// instructions into the ready-list.
     template <typename ReadyListType>
     void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
+      assert(!DisableScheduling && "Trying to schedule when disabled");
       SD->IsScheduled = true;
       LLVM_DEBUG(dbgs() << "SLP:   schedule " << *SD << "\n");
 
       for (ScheduleData *BundleMember = SD; BundleMember;
            BundleMember = BundleMember->NextInBundle) {
         if (BundleMember->Inst != BundleMember->OpValue)
           continue;
 
struct BlockScheduling {
     /// cyclic dependencies. This is only a dry-run, no instructions are
     /// actually moved at this stage.
     /// \returns the scheduling bundle. The returned Optional value is non-None
     /// if \p VL is allowed to be scheduled.
     Optional<ScheduleData *>
     tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
                       const InstructionsState &S);
 
+    /// \Returns an uninitialized ScheduleBundle. This is needed when disabling
+    /// the scheduler because a non-null ScheduleData bundle is used to
+    /// determine whether a TreeEntry is marked as vectorizable.
+    static ScheduleData *getDummyBundle() {
+      static ScheduleData SD;
+      return &SD;
+    }
+
     /// Un-bundles a group of instructions.
     void cancelScheduling(ArrayRef<Value *> VL, Value *OpValue);
 
     /// Allocates schedule data chunk.
     ScheduleData *allocateScheduleDataChunks();
 
     /// Extends the scheduling region so that V is inside the region.
     /// \returns true if the region size is within the limit.
struct BlockScheduling {
     /// The maximum size allowed for the scheduling region.
     int ScheduleRegionSizeLimit = ScheduleRegionSizeBudget;
 
     /// The ID of the scheduling region. For a new vectorization iteration this
     /// is incremented which "removes" all ScheduleData from the region.
     /// Make sure that the initial SchedulingRegionID is greater than the
     /// initial SchedulingRegionID in ScheduleData (which is 0).
     int SchedulingRegionID = 1;
+
+    /// This is set to true if we need to skip scheduling for this block.
+    bool DisableScheduling = false;
   };
 
   /// Attaches the BlockScheduling structures to basic blocks.
   MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
 
   /// Performs the "real" scheduling. Done before vectorization is actually
   /// performed in a basic block.
   void scheduleBlock(BlockScheduling *BS);
void BoUpSLP::buildTree(ArrayRef<Value *> Roots,
                         ArrayRef<Value *> UserIgnoreLst) {
   deleteTree();
   UserIgnoreList = UserIgnoreLst;
   if (!allSameType(Roots))
     return;
   buildTree_rec(Roots, 0, EdgeInfo());
 }
 
+InstructionCost BoUpSLP::buildTreeFastAndGetCost(ArrayRef<Value *> Roots,
+                                                 Optional<unsigned> MaxSize,
+                                                 bool DisableScheduling) {
+  deleteTree();
+  MaxTreeSize = MaxSize;
+  ForceDisableScheduling = DisableScheduling;
+  if (!allSameType(Roots))
+    return InstructionCost::getMax();
+
+  buildTree_rec(Roots, 0, EdgeInfo());
+
+  if (isTreeTinyAndNotFullyVectorizable())
+    return InstructionCost::getMax();
+  reorderTopToBottom();
+  reorderBottomToTop(!isa<InsertElementInst>(Roots.front()));
+  buildExternalUses();
+  computeMinimumValueSizes();
+  return getTreeCost();
+}
+
 namespace {
 /// Tracks the state we can represent the loads in the given sequence.
 enum class LoadsState { Gather, Vectorize, ScatterVectorize };
 } // anonymous namespace
 
 /// Checks if the given array of loads can be represented as a vectorized,
 /// scatter or just simple gather.
 static LoadsState canVectorizeLoads(ArrayRef<Value *> VL, const Value *VL0,
if (auto *LI = dyn_cast<LoadInst>(V)) {
     }
     Key = hash_combine(hash_value(I->getParent()), Key);
   }
   return std::make_pair(Key, SubKey);
 }
 
 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
                             const EdgeInfo &UserTreeIdx) {
+  // If we are building a fast approximate tree, then early return once we reach
+  // the tree size limit.
+  if (MaxTreeSize && VectorizableTree.size() >= *MaxTreeSize) {
+    LLVM_DEBUG(dbgs() << "SLP: Reached max tree size " << *MaxTreeSize
+                      << ".\n");
+    return;
+  }
   assert((allConstant(VL) || allSameType(VL)) && "Invalid types!");
 
   SmallVector<int> ReuseShuffleIndicies;
   SmallVector<Value *> UniqueValues;
   auto &&TryToFindDuplicates = [&VL, &ReuseShuffleIndicies, &UniqueValues,
                                 &UserTreeIdx,
                                 this](const InstructionsState &S) {
     // Check that every instruction appears once in this bundle.
void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
   if (!TryToFindDuplicates(S))
     return;
 
   auto &BSRef = BlocksSchedules[BB];
   if (!BSRef)
     BSRef = std::make_unique<BlockScheduling>(BB);
 
   BlockScheduling &BS = *BSRef;
+  BS.DisableScheduling = ForceDisableScheduling;
 
-  Optional<ScheduleData *> Bundle = BS.tryScheduleBundle(VL, this, S);
+  Optional<ScheduleData *> Bundle = !ForceDisableScheduling
+                                        ? BS.tryScheduleBundle(VL, this, S)
+                                        : BlockScheduling::getDummyBundle();
 #ifdef EXPENSIVE_CHECKS
   // Make sure we didn't break any internal invariants
   BS.verify();
 #endif
-  if (!Bundle) {
+  if (!ForceDisableScheduling && !Bundle) {
     LLVM_DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
     assert((!BS.getScheduleData(VL0) ||
             !BS.getScheduleData(VL0)->isPartOfBundle()) &&
            "tryScheduleBundle should cancelScheduling on failure");
     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
                  ReuseShuffleIndicies);
     return;
   }
-  LLVM_DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
+  LLVM_DEBUG(dbgs() << (ForceDisableScheduling
+                            ? "SLP: Scheduling was disabled.\n"
+                            : "SLP: We are able to schedule this bundle.\n"));
 
   unsigned ShuffleOrOp = S.isAltShuffle() ?
                 (unsigned) Instruction::ShuffleVector : S.getOpcode();
   switch (ShuffleOrOp) {
     case Instruction::PHI: {
       auto *PH = cast<PHINode>(VL0);
 
       // Check for terminator values (e.g. invoke).
BoUpSLP::BlockScheduling::buildBundle(ArrayRef<Value *> VL) {
   return Bundle;
 }
 
 // Groups the instructions to a bundle (which is then a single scheduling entity)
 // and schedules instructions until the bundle gets ready.
 Optional<BoUpSLP::ScheduleData *>
 BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
                                             const InstructionsState &S) {
+  assert(!DisableScheduling && "Trying to schedule when disabled");
   // No need to schedule PHIs, insertelement, extractelement and extractvalue
   // instructions.
   if (isa<PHINode>(S.OpValue) || isVectorLikeInstWithConstOps(S.OpValue) ||
       doesNotNeedToSchedule(VL))
     return nullptr;
 
   // Initialize the instruction bundle.
   Instruction *OldScheduleEnd = ScheduleEnd;
if (!Bundle->isReady()) {
     cancelScheduling(VL, S.OpValue);
     return None;
   }
   return Bundle;
 }
 
 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL,
                                                 Value *OpValue) {
+  // Early return if scheduling is disabled.
+  if (DisableScheduling)
+    return;
   if (isa<PHINode>(OpValue) || isVectorLikeInstWithConstOps(OpValue) ||
       doesNotNeedToSchedule(VL))
     return;
 
   if (doesNotNeedToBeScheduled(OpValue))
     OpValue = *find_if_not(VL, doesNotNeedToBeScheduled);
   ScheduleData *Bundle = getScheduleData(OpValue);
   LLVM_DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");

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/pr48879-sroa.ll

 ;
 ; AVX-LABEL: @compute_min(
 ; AVX-NEXT:  entry:
 ; AVX-NEXT:    [[TMP0:%.*]] = load i16, ptr [[Y:%.*]], align 2
 ; AVX-NEXT:    [[TMP1:%.*]] = load i16, ptr [[X:%.*]], align 2
 ; AVX-NEXT:    [[TMP2:%.*]] = tail call i16 @llvm.smin.i16(i16 [[TMP0]], i16 [[TMP1]])
 ; AVX-NEXT:    [[ARRAYIDX_I_I_1:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 1
 ; AVX-NEXT:    [[ARRAYIDX_I_I10_1:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 1
-; AVX-NEXT:    [[TMP3:%.*]] = load i16, ptr [[ARRAYIDX_I_I10_1]], align 2
-; AVX-NEXT:    [[TMP4:%.*]] = load i16, ptr [[ARRAYIDX_I_I_1]], align 2
+; AVX-NEXT:    [[ARRAYIDX_I_I_3:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 3
+; AVX-NEXT:    [[ARRAYIDX_I_I10_3:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 3
+; AVX-NEXT:    [[TMP3:%.*]] = load i16, ptr [[ARRAYIDX_I_I10_3]], align 2
+; AVX-NEXT:    [[TMP4:%.*]] = load i16, ptr [[ARRAYIDX_I_I_3]], align 2
 ; AVX-NEXT:    [[TMP5:%.*]] = tail call i16 @llvm.smin.i16(i16 [[TMP3]], i16 [[TMP4]])
-; AVX-NEXT:    [[ARRAYIDX_I_I_2:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 2
-; AVX-NEXT:    [[ARRAYIDX_I_I10_2:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 2
 ; AVX-NEXT:    [[ARRAYIDX_I_I_4:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 4
 ; AVX-NEXT:    [[ARRAYIDX_I_I10_4:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 4
 ; AVX-NEXT:    [[TMP6:%.*]] = load i16, ptr [[ARRAYIDX_I_I10_4]], align 2
 ; AVX-NEXT:    [[TMP7:%.*]] = load i16, ptr [[ARRAYIDX_I_I_4]], align 2
 ; AVX-NEXT:    [[TMP8:%.*]] = tail call i16 @llvm.smin.i16(i16 [[TMP6]], i16 [[TMP7]])
 ; AVX-NEXT:    [[ARRAYIDX_I_I_5:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 5
 ; AVX-NEXT:    [[ARRAYIDX_I_I10_5:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 5
-; AVX-NEXT:    [[TMP9:%.*]] = load i16, ptr [[ARRAYIDX_I_I10_5]], align 2
-; AVX-NEXT:    [[TMP10:%.*]] = load i16, ptr [[ARRAYIDX_I_I_5]], align 2
+; AVX-NEXT:    [[ARRAYIDX_I_I_7:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 7
+; AVX-NEXT:    [[ARRAYIDX_I_I10_7:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 7
+; AVX-NEXT:    [[TMP9:%.*]] = load i16, ptr [[ARRAYIDX_I_I10_7]], align 2
+; AVX-NEXT:    [[TMP10:%.*]] = load i16, ptr [[ARRAYIDX_I_I_7]], align 2
 ; AVX-NEXT:    [[TMP11:%.*]] = tail call i16 @llvm.smin.i16(i16 [[TMP9]], i16 [[TMP10]])
-; AVX-NEXT:    [[ARRAYIDX_I_I_6:%.*]] = getelementptr inbounds [8 x i16], ptr [[X]], i64 0, i64 6
-; AVX-NEXT:    [[ARRAYIDX_I_I10_6:%.*]] = getelementptr inbounds [8 x i16], ptr [[Y]], i64 0, i64 6
-; AVX-NEXT:    [[TMP12:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I10_2]], align 2
-; AVX-NEXT:    [[TMP13:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I_2]], align 2
+; AVX-NEXT:    [[RETVAL_SROA_4_0_INSERT_EXT:%.*]] = zext i16 [[TMP5]] to i64
+; AVX-NEXT:    [[RETVAL_SROA_4_0_INSERT_SHIFT:%.*]] = shl nuw i64 [[RETVAL_SROA_4_0_INSERT_EXT]], 48
+; AVX-NEXT:    [[TMP12:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I10_1]], align 2
+; AVX-NEXT:    [[TMP13:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I_1]], align 2
 ; AVX-NEXT:    [[TMP14:%.*]] = call <2 x i16> @llvm.smin.v2i16(<2 x i16> [[TMP12]], <2 x i16> [[TMP13]])
 ; AVX-NEXT:    [[TMP15:%.*]] = zext <2 x i16> [[TMP14]] to <2 x i64>
-; AVX-NEXT:    [[TMP16:%.*]] = shl nuw <2 x i64> [[TMP15]], <i64 32, i64 48>
-; AVX-NEXT:    [[TMP17:%.*]] = extractelement <2 x i64> [[TMP16]], i32 0
-; AVX-NEXT:    [[TMP18:%.*]] = extractelement <2 x i64> [[TMP16]], i32 1
-; AVX-NEXT:    [[RETVAL_SROA_3_0_INSERT_INSERT:%.*]] = or i64 [[TMP18]], [[TMP17]]
-; AVX-NEXT:    [[RETVAL_SROA_2_0_INSERT_EXT:%.*]] = zext i16 [[TMP5]] to i64
-; AVX-NEXT:    [[RETVAL_SROA_2_0_INSERT_SHIFT:%.*]] = shl nuw nsw i64 [[RETVAL_SROA_2_0_INSERT_EXT]], 16
-; AVX-NEXT:    [[RETVAL_SROA_2_0_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_3_0_INSERT_INSERT]], [[RETVAL_SROA_2_0_INSERT_SHIFT]]
+; AVX-NEXT:    [[TMP16:%.*]] = shl nuw nsw <2 x i64> [[TMP15]], <i64 16, i64 32>
+; AVX-NEXT:    [[TMP17:%.*]] = extractelement <2 x i64> [[TMP16]], i32 1
+; AVX-NEXT:    [[RETVAL_SROA_3_0_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_4_0_INSERT_SHIFT]], [[TMP17]]
+; AVX-NEXT:    [[TMP18:%.*]] = extractelement <2 x i64> [[TMP16]], i32 0
+; AVX-NEXT:    [[RETVAL_SROA_2_0_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_3_0_INSERT_INSERT]], [[TMP18]]
 ; AVX-NEXT:    [[RETVAL_SROA_0_0_INSERT_EXT:%.*]] = zext i16 [[TMP2]] to i64
 ; AVX-NEXT:    [[RETVAL_SROA_0_0_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_2_0_INSERT_INSERT]], [[RETVAL_SROA_0_0_INSERT_EXT]]
 ; AVX-NEXT:    [[DOTFCA_0_INSERT:%.*]] = insertvalue { i64, i64 } poison, i64 [[RETVAL_SROA_0_0_INSERT_INSERT]], 0
-; AVX-NEXT:    [[TMP19:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I10_6]], align 2
-; AVX-NEXT:    [[TMP20:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I_6]], align 2
+; AVX-NEXT:    [[RETVAL_SROA_9_8_INSERT_EXT:%.*]] = zext i16 [[TMP11]] to i64
+; AVX-NEXT:    [[RETVAL_SROA_9_8_INSERT_SHIFT:%.*]] = shl nuw i64 [[RETVAL_SROA_9_8_INSERT_EXT]], 48
+; AVX-NEXT:    [[TMP19:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I10_5]], align 2
+; AVX-NEXT:    [[TMP20:%.*]] = load <2 x i16>, ptr [[ARRAYIDX_I_I_5]], align 2
 ; AVX-NEXT:    [[TMP21:%.*]] = call <2 x i16> @llvm.smin.v2i16(<2 x i16> [[TMP19]], <2 x i16> [[TMP20]])
 ; AVX-NEXT:    [[TMP22:%.*]] = zext <2 x i16> [[TMP21]] to <2 x i64>
-; AVX-NEXT:    [[TMP23:%.*]] = shl nuw <2 x i64> [[TMP22]], <i64 32, i64 48>
-; AVX-NEXT:    [[TMP24:%.*]] = extractelement <2 x i64> [[TMP23]], i32 0
-; AVX-NEXT:    [[TMP25:%.*]] = extractelement <2 x i64> [[TMP23]], i32 1
-; AVX-NEXT:    [[RETVAL_SROA_8_8_INSERT_INSERT:%.*]] = or i64 [[TMP25]], [[TMP24]]
-; AVX-NEXT:    [[RETVAL_SROA_7_8_INSERT_EXT:%.*]] = zext i16 [[TMP11]] to i64
-; AVX-NEXT:    [[RETVAL_SROA_7_8_INSERT_SHIFT:%.*]] = shl nuw nsw i64 [[RETVAL_SROA_7_8_INSERT_EXT]], 16
-; AVX-NEXT:    [[RETVAL_SROA_7_8_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_8_8_INSERT_INSERT]], [[RETVAL_SROA_7_8_INSERT_SHIFT]]
+; AVX-NEXT:    [[TMP23:%.*]] = shl nuw nsw <2 x i64> [[TMP22]], <i64 16, i64 32>
+; AVX-NEXT:    [[TMP24:%.*]] = extractelement <2 x i64> [[TMP23]], i32 1
+; AVX-NEXT:    [[RETVAL_SROA_8_8_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_9_8_INSERT_SHIFT]], [[TMP24]]
+; AVX-NEXT:    [[TMP25:%.*]] = extractelement <2 x i64> [[TMP23]], i32 0
+; AVX-NEXT:    [[RETVAL_SROA_7_8_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_8_8_INSERT_INSERT]], [[TMP25]]
 ; AVX-NEXT:    [[RETVAL_SROA_5_8_INSERT_EXT:%.*]] = zext i16 [[TMP8]] to i64
 ; AVX-NEXT:    [[RETVAL_SROA_5_8_INSERT_INSERT:%.*]] = or i64 [[RETVAL_SROA_7_8_INSERT_INSERT]], [[RETVAL_SROA_5_8_INSERT_EXT]]
 ; AVX-NEXT:    [[DOTFCA_1_INSERT:%.*]] = insertvalue { i64, i64 } [[DOTFCA_0_INSERT]], i64 [[RETVAL_SROA_5_8_INSERT_INSERT]], 1
 ; AVX-NEXT:    ret { i64, i64 } [[DOTFCA_1_INSERT]]
 ;
 entry:
   %0 = load i16, ptr %y, align 2
   %1 = load i16, ptr %x, align 2

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

 
 attributes #0 = { "unsafe-fp-math"="true" }
 
 ; This test checks that root steering works and that the code gets vectorized.
 
 define void @root_steering() {
 ; CHECK-LABEL: @root_steering(
 ; CHECK-NEXT:  bb:
-; CHECK-NEXT:    [[CHAIN2_2:%.*]] = fadd double 4.000000e-01, 5.000000e-01
-; CHECK-NEXT:    [[CHAIN2_1:%.*]] = fmul double 3.000000e-01, [[CHAIN2_2]]
-; CHECK-NEXT:    [[ROOT5:%.*]] = fadd double 2.000000e-01, [[CHAIN2_1]]
 ; CHECK-NEXT:    [[ROOT3:%.*]] = fmul double 3.000000e-01, 2.000000e-01
 ; CHECK-NEXT:    [[MUL:%.*]] = fmul double [[ROOT3]], 1.000000e-01
 ; CHECK-NEXT:    [[CHAINB_3:%.*]] = fadd double 3.000000e-01, 4.000000e-01
 ; CHECK-NEXT:    [[CHAINB_2:%.*]] = fmul double 2.000000e-01, [[CHAINB_3]]
-; CHECK-NEXT:    [[CHAINB_1:%.*]] = fadd double 1.000000e-01, [[CHAINB_2]]
-; CHECK-NEXT:    [[ROOT4:%.*]] = fmul double [[MUL]], [[CHAINB_1]]
-; CHECK-NEXT:    [[ROOT2:%.*]] = fadd double 1.000000e-01, [[ROOT4]]
-; CHECK-NEXT:    [[ROOT1:%.*]] = fmul double [[ROOT3]], [[ROOT5]]
-; CHECK-NEXT:    [[DIV:%.*]] = fdiv double [[ROOT1]], [[ROOT2]]
+; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> <double 5.000000e-01, double poison>, double [[CHAINB_2]], i32 1
+; CHECK-NEXT:    [[TMP1:%.*]] = fadd <2 x double> <double 4.000000e-01, double 1.000000e-01>, [[TMP0]]
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> <double 3.000000e-01, double poison>, double [[MUL]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = fmul <2 x double> [[TMP2]], [[TMP1]]
+; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> <double 2.000000e-01, double 1.000000e-01>, [[TMP3]]
+; CHECK-NEXT:    [[TMP5:%.*]] = extractelement <2 x double> [[TMP4]], i32 0
+; CHECK-NEXT:    [[ROOT1:%.*]] = fmul double [[ROOT3]], [[TMP5]]
+; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <2 x double> [[TMP4]], i32 1
+; CHECK-NEXT:    [[DIV:%.*]] = fdiv double [[ROOT1]], [[TMP6]]
 ; CHECK-NEXT:    [[SEED:%.*]] = fcmp ogt double [[DIV]], 3.000000e-01
 ; CHECK-NEXT:    ret void
 ;
 bb:
   %chain2_2 = fadd double 0.4, 0.5
   %chain2_1 = fmul double 0.3, %chain2_2
   %root5 = fadd double 0.2, %chain2_1