[SLP] Refactoring of the operand reordering code.

[vporpo]

Summary

This is a refactoring patch which should have all the functionality of the current code. Its goal is twofold:
i. Cleanup and simplify the reordering code, and
ii. Generalize reordering so that it will work for an arbitrary number of operands, not just 2.

This is the second patch in a series of patches that will enable operand reordering across chains of operations. An example of this was presented in EuroLLVM'18 https://www.youtube.com/watch?v=gIEn34LvyNo .

[RKSimon]

Awesome! Some initial thoughts - you maybe want to checkout D57059 as @ABataev is looking at adding UNDEF support to handle non-power2 types which will probably need to work with VLOperands

lib/Transforms/Vectorize/SLPVectorizer.cpp

616

Separate pre-commit?

636

Maybe OperandMode or OperandType?

638

Its not necessarily the same opcode (might be altopcode etc.)

906

Better to use Optional<unsigned> for failure?

910

Could this be static?

912

ArrayRef<OpMode>

915

Do we need this? Maybe just put inside reorderInputsAccordingToOpcode?

[RKSimon]

lib/Transforms/Vectorize/SLPVectorizer.cpp

640

Matching for extractelement is also an issue: https://bugs.llvm.org/show_bug.cgi?id=41304

[vporpo]

I also rebased to support the commutative predicates of D59992.

lib/Transforms/Vectorize/SLPVectorizer.cpp

636

I am trying to avoid 'Type' because it might get confused with LLVM Type. How about ReorderingMode?

638

Correct, I will update the comment.

640

Good point, but let's implement it in a separate patch.

910

It could, but we need to pass DL and SE for isConsecutiveAccess().

915

I agree, it is kind of redundant right now.

I have placed it in a standalone function because there will be a second call site for it in the follow-up patch that implements operand reordering across more than 2 operand vectors.

[RKSimon]

lib/Transforms/Vectorize/SLPVectorizer.cpp

911

I don't think \reorder is a doxygen tag?

[vporpo]

Fixed doxygen tags.

[RKSimon]

lib/Transforms/Vectorize/SLPVectorizer.cpp

640

@spatel has done this in instcombine which should be good enough.

676

This isn't used yet - can it wait until you need it? Also - should you use ArrayRef?

742

If this is now the only use of isCommutative then maybe merge them? Not sure if it needs to be inside VLOperands

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

676

This must be an ArrayRef definitely

712

Provide default initializers

728

{} -> = default;

795

const member function

804

make function const

[vporpo]

Addressed the comments.

[vporpo]

Rebased + some minor changes.

[RKSimon]

test/Transforms/SLPVectorizer/X86/crash_smallpt.ll

35

This looks like a regression - we're losing an all constant operand here (plus the TMP1 no longer simplifies to a single scalar load).

test/Transforms/SLPVectorizer/X86/operandorder.ll

47

Hmm - these tests are called 'preserve_broadcast' and we're not preserving the broadcasts any more.... This might not be a bad thing but it'd be good to confirm (and possibly rename the tests if everything is good)

[vporpo]

Updated getBestOperand() to better handle undefs. This fixes the regression in crash_smallpt.ll.

[vporpo]

I am not sure how to proceed with the operandorder.ll test. @ABataev do you know why we would give higher priority to broadcasts?

test/Transforms/SLPVectorizer/X86/crash_smallpt.ll

35

Good catch.
The reason was that we were skipping undefs when trying to match an instruction in getBestOperand().
I updated the code to accept Undefs as a secondary option.
In a later patch we should also add a new ReorderingMode for Undefs.

test/Transforms/SLPVectorizer/X86/operandorder.ll

47

I am not sure why we would prefer to build a broadcast instead of vectorizing the loads.
@ABataev any idea about this?

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

707

Remove semicolon

796

auto &->const OperandDataVec & for better readability (it is not very easy to deduce the type)

3053

auto & to real type

3192

Maybу it would be better to encapsulate all this reordering in the VLOperands class rather than exposing some low-level transformators like swap etc.?

test/Transforms/SLPVectorizer/X86/operandorder.ll

47

I agree, that the vectorization of loads is better.

[RKSimon]

test/Transforms/SLPVectorizer/X86/operandorder.ll

47

OK - rename as "shuffle_vs_broadcast" or something?

[vporpo]

Addressed the comments and also moved the reordering-related functions inside the VLOperands class.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

3192

Good point, I don't see any reason why reordering should not be a method of VLOperands. I moved all the reordering related methods inside VLOperands.

[RKSimon]

No more comments from me @ABataev ?

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

636

Seems to me, this enum is used only in VLOperands class. Better to move it to class itself.

726–727

Better to use references rather than pointers

729

Seems to me, this constructor is not used. Transform it into deleted rather than default.

769

Make it private, since it is used only in class members

855

I don't think you need braces here

968

Private?

971

Private?

974

Private?

979

Check these memeber functions and make private as much as possible

994

Preallocate memory for this array since you know the size (OpsVec[OpIdx].size())

[vporpo]

Addressed @ABataev 's comments.

lib/Transforms/Vectorize/SLPVectorizer.cpp

729

It is used by OpsVec.resize() so I can't delete it.

968

I guess we can keep everything private for now except reorder() and getVL()

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

681

Use /// style of comments here

841

Use preincrement

906

Hmm, can't find the definition of this function.

907

Better to reserve the space when constructing the variable

909

You should not push here, instead assign to the preallocated elements.

991

return StringRef.

1024

Do not use autos here and in the inner loop since it is hard to deduce the real type

3039

Could you make it static? It is strange to see const reorder... function.

[vporpo]

Addressed the latest comments.

lib/Transforms/Vectorize/SLPVectorizer.cpp

3039

Well, it is a member function in order to avoid passing DL and SE as arguments on every call site. Anyway, either is fine with me.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

955

Maybe set to Failed here just in case, to prevent possible compiler crash?

984

Shall we undo previously performed swaps in this case, if we could do some reordering earlier?

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

I don't think undoing the swaps would help much. Following the reordering strategy for as long as we can without undoing on failure may actually help sometimes. For example, if our strategy is to look for the same opcode and half-way through the lanes we can no longer match it, we should still keep the order for the ones found so far, because we could potentially still vectorize these operands with a smaller vector length. If we undo them, that will not be possible.

Revisiting the failed operands and trying again with a different strategy could help. But I think we should try implement such back-tracking approaches in a separate optimization patch.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

Then, maybe, you should continue trying to reorder other elements in the same lane, and should not mark it as Failed too early? You can save the value somewhere in the temp array and update the original element to Failed state after the loop.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

I am not sure I follow. I think we are not on the same page on how the ReorderingMode strategies work. Let me explain.
The ReorderingModes (e.g., Opcode or Failed) are not per-lane, but per operand index (0 or 1 for now).
So even if an operand index is marked as "Failed" at some lane, the rest of the operands of that lane are still trying to reorder the elements.
The idea is that by marking an operand index as "Failed", we are announcing that it has the lowest priority in picking a value. This makes sense, because a "Failed" operand index is guaranteed not to form a full-length vector, but maybe other operands can still succeed, so they should have higher priority in selecting the operand values.

For example, operand 0 might be initialized with the "Opcode" strategy. Then, say that at lane 3 we can no longer find a matching opcode for operand 0, and operand 0 is therefore marked as "Failed". This means that from this point on, getBestOperand() will always return None for operand 0 on any lane, as operand 0 cannot possibly form a full-size vector. If operand 1 has not failed yet, it will be the one selecting the operand values, not operand 0. This is a good strategy, as operand 1may still succeed in forming a full-size vector.

Does this make sense?

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

Yeah, but it may lead to some non-stable results. At first, we anounce that the operation has a high priority and reorder elements according to this high-pripority. Then, somewhere in the middle, we change to it to lower priority and change the reording. Is this really expected behavior? Or maybe it is better to make some preliminary analysis to identify the most successful strategy and only after that do the real reordering?

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

Ah yes, I agree. Ideally we should back-track and re-decide on the strategy, given that we failed half-way through.
But if we don't back-track and we need to decide in one go, then I don't think there is anything really wrong with what we are doing now. I think it fully covers the functionality of the previous implementation, without adding complexity.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

But I think we should improve previous implementation, if this possible, agree? And this is possible. We can try to produce more predictable results rather than end up with the mess in some corner cases. I think this is really worth it.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

Yes, I fully agree, and I will be happy to work on it. But why not do it in a separate patch? This one is a refactoring patch that keeps the reordering more or less equivalent to the existing code. The follow-up patch can focus on improving upon this with specific test cases etc.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

Hmm, it does not look like a simple NFC patch, since it is already changes the behavior of the compiler. Why not to fix this problem right now, if the main part is implemented already? Make it as a simple 2-pass transformation: preliminary analysis and then actual reordering. We don't need to do the backtracking in this case.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

984

OK, how about this one? If the first pass fails, then we perform a second pass using the modes of the first one. If some operand index failed in the first pass, it will have low priority in the second pass for all lanes.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

1003

I think the first pass should not do any swaps.

[vporpo]

lib/Transforms/Vectorize/SLPVectorizer.cpp

1003

Well, if we don't do the swap, then getBestOperand() won't work, as it relies on the state of OpsVec for checking the previous lane vs the current one. We could potentially use some other helper structure to avoid updating the state in OpsVec, but that would complicate the code quite a bit.

Also, I don't see any harm in applying the reordering in the first pass. The worst that can happen is that the order in OpsVec will change in the second pass. Am I missing out something here?

[ABataev]

Seems good with a nit

lib/Transforms/Vectorize/SLPVectorizer.cpp

1000

Enclose substatement into braces

[vporpo]

Thank you for the reviews. @RKSimon any more comments ?

[RKSimon]

In D59973#1468106, @vporpo wrote:

Thank you for the reviews. @RKSimon any more comments ?

LGTM - cheers

[vporpo]

Great, thanks! Please commit the patch , I don't have commit access.

lib/Transforms/Vectorize/SLPVectorizer.cpp

public:
   /// (i) the user TreeEntry index, and
   /// (ii) the index of the edge.
   struct EdgeInfo {
     EdgeInfo() = default;
     /// The index of the user TreeEntry in VectorizableTree.
     int Idx = -1;
     /// The operand index of the use.
     unsigned EdgeIdx = UINT_MAX;
-#ifndef NDEBUG
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     friend inline raw_ostream &operator<<(raw_ostream &OS,
                                           const BoUpSLP::EdgeInfo &EI) {
       EI.dump(OS);
       return OS;
     }
     /// Debug print.
     void dump(raw_ostream &OS) const {
       OS << "{User:" << Idx << " EdgeIdx:" << EdgeIdx << "}";
     }
     LLVM_DUMP_METHOD void dump() const { dump(dbgs()); }
 #endif
   };
 
+  /// During operand reordering, we are trying to select the operand at lane
+  /// that matches best with the operand at the neighboring lane. Our selection
+  /// is based on the type of value we are looking for. For example, if the
+  /// neighboring lane has a load, we need to look for a load that is accessing
+  /// a consecutive address.
+  /// These strategies are summarized in the 'OpMode' enumerator.
+  enum class OpMode {
+    Load,     // Matching loads to consecutive memory addresses
+    Opcode,   // Matching instructions of the same opcode
+    Constant, // Matching constants
+    Splat,    // Matching the same instruction multiple times (broadcast)
+    Failed,   // We failed to create a vectorizable group
+  };
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+  LLVM_DUMP_METHOD static const char *getModeStr(OpMode Mode) {
+    switch (Mode) {
+    case OpMode::Load:
+      return "Load";
+    case OpMode::Opcode:
+      return "Opcode";
+    case OpMode::Constant:
+      return "Constant";
+    case OpMode::Splat:
+      return "Splat";
+    case OpMode::Failed:
+      return "Failed";
+    }
+    llvm_unreachable("Unimplemented Mode");
+  }
+
+  LLVM_DUMP_METHOD static raw_ostream &printMode(OpMode Mode, raw_ostream &OS) {
+    return OS << getModeStr(Mode);
+  }
+
+  /// Debug print.
+  LLVM_DUMP_METHOD static void dumpMode(OpMode Mode) {
+    printMode(Mode, dbgs());
+  }
+
+  friend raw_ostream &operator<<(raw_ostream &OS, OpMode Mode) {
+    return printMode(Mode, OS);
+  }
+
+  LLVM_DUMP_METHOD static void
+  dumpModeVec(const SmallVectorImpl<OpMode> &ModeVec) {
+    for (unsigned OpIdx = 0, E = ModeVec.size(); OpIdx != E; ++OpIdx)
+      dbgs() << OpIdx << ". " << ModeVec[OpIdx] << "\n";
+  }
+#endif
+
+  /// A helper data structure to hold the operands of a vector of instructions.
+  /// This supports a fixed vector length for all operand vectors.
+  class VLOperands {
+    /// For each operand we need (i) the value, and (ii) the opcode that it
+    /// would be attached to if the expression was in a left-linearized form.
+    /// This is required to avoid illegal operand reordering.
+    /// For example:
+    /// \verbatim
+    ///                         0 Op1
+    ///                         |/
+    /// Op1 Op2   Linearized    + Op2
+    ///   \ /     ---------->   |/
+    ///    -                    -
+    ///
+    /// Op1 - Op2            (0 + Op1) - Op2
+    /// \endverbatim
+    ///
+    /// Value Op1 is attached to a '+' operation, and Op2 to a '-'.
+    ///
+    /// Another way to think of this is to track all the operations across the
+    /// path from the operand all the way to the root of the tree and to
+    /// calculate the operation that corresponds to this path. For example, the
+    /// path from Op2 to the root crosses the RHS of the '-', therefore the
+    /// corresponding operation is a '-' (which matches the one in the
+    /// linearized tree, as shown above).
+    ///
+    /// For lack of a better term, we refer to this operation as Accumulated
+    /// Path Operation (APO).
+    struct OperandData {
+      /// The operand value.
+      Value *V;
+      /// TreeEntries only allow a single opcode, or an alternate sequence of
+      /// them (e.g, +, -). Therefore, we can safely use a boolean value for the
+      /// APO. It is set to 'true' if 'V' is attached to an inverse operation
+      /// in the left-linearized form (e.g., Sub/Div), and 'false' otherwise
+      /// (e.g., Add/Mul)
+      bool APO;
+      /// Helper data for the reordering function.
+      bool IsUsed;
+    };
+    using OperandDataVec = SmallVector<OperandData, 2>;
+
+    /// A vector of operand vectors.
+    SmallVector<OperandDataVec, 4> OpsVec;
+
+  public:
+    VLOperands() {}
+    /// Initialize with all the operands of the instruction vector \p VL.
+    VLOperands(ArrayRef<Value *> VL) {
+        // Append all the operands of VL.
+        appendOperandsOfVL(VL);
+    }
+
+    /// \Returns true if \p I is an inverse operation with respect to a
+    /// corresponding commutative operation. For example, this it will return
+    /// true for a Sub because it is the inverse operation of an Add.
+    static bool isInverseOperation(Instruction *I) {
+      // Since operand reordering is performed on groups of commutative
+      // operations or alternating sequences (e.g., +, -), we can safely tell
+      // the inverse operations by checking commutativity.
+      return !I->isCommutative();
+    }
+
+    /// Go through the instructions in VL and append their operands.
+    void appendOperandsOfVL(ArrayRef<Value *> VL) {
+      assert(!VL.empty() && "Bad VL");
+      assert((empty() || VL.size() == getNumLanes()) &&
+             "Expected same number of lanes");
+      assert(isa<Instruction>(VL[0]) && "Expected instruction");
+      unsigned NumOperands = cast<Instruction>(VL[0])->getNumOperands();
+      OpsVec.resize(NumOperands);
+      unsigned NumLanes = VL.size();
+      for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
+        OpsVec[OpIdx].resize(NumLanes);
+        for (unsigned Lane = 0; Lane != NumLanes; ++Lane) {
+          assert(isa<Instruction>(VL[Lane]) && "Expected instruction");
+          // Our tree has just 3 nodes: the root and two operands.
+          // It is therefore trivial to get the APO. We only need to check the
+          // opcode of VL[0] and whether the operand at OpIdx is the LHS or RHS
+          // operand. The LHS operand of both add and sub is nevere attached to
+          // an inversese operation in the linearized form, therefore its APO is
+          // false. The RHS is ture only if VL[Lane] is an inverse operation.
+          bool APO = (OpIdx == 0)
+                         ? false
+                         : isInverseOperation(cast<Instruction>(VL[Lane]));
+          OpsVec[OpIdx][Lane] = {cast<Instruction>(VL[Lane])->getOperand(OpIdx),
+                                 APO, false};
+        }
+      }
+    }
+
+    /// Swap the operand at \p OpIdx1 with that one at \p OpIdx2.
+    void swap(unsigned OpIdx1, unsigned OpIdx2, unsigned Lane) {
+      std::swap(OpsVec[OpIdx1][Lane], OpsVec[OpIdx2][Lane]);
+    }
+
+    /// \returns the number of operands.
+    unsigned getNumOperands() const { return OpsVec.size(); }
+
+    /// \returns the number of lanes.
+    unsigned getNumLanes() const { return OpsVec[0].size(); }
+
+    /// \returns the operand data at \p OpIdx and \p Lane.
+    OperandData &getData(unsigned OpIdx, unsigned Lane) {
+      return OpsVec[OpIdx][Lane];
+    }
+
+    /// \returns the operand data at \p OpIdx and \p Lane. Const version.
+    const OperandData &getData(unsigned OpIdx, unsigned Lane) const {
+      return OpsVec[OpIdx][Lane];
+    }
+
+    /// \returns the operand value at \p OpIdx and \p Lane.
+    Value *getValue(unsigned OpIdx, unsigned Lane) {
+      return getData(OpIdx, Lane).V;
+    }
+
+    /// \returns true if the data structure is empty.
+    bool empty() const { return OpsVec.empty(); }
+
+    /// \Returns a value vector with the operands across all lanes for the
+    /// opearnd at \p OpIdx.
+    ValueList getVL(unsigned OpIdx) {
+      ValueList OpVL;
+      for (auto &OpData : OpsVec[OpIdx])
+        OpVL.push_back(OpData.V);
+      return OpVL;
+    }
+
+    /// \Returns the maximum number of operands that are allowed to be reordered
+    /// for \p Lane. This is used as a heuristic for selecting the first lane to
+    /// start operand reordering.
+    unsigned getMaxNumOperandsThatCanBeReordered(unsigned Lane) const {
+      unsigned CntTrue = 0;
+      unsigned NumOperands = getNumOperands();
+      // Operands with the same APO can be reordered. We therefore need to count
+      // how many of them we have for each APO, like this: Cnt[APO] = x.
+      // Since we only have two APOs, namely true and false, we can avoid using
+      // a map. Instead we can simply count the number of operands that
+      // correspond to one of them (in this case the 'true' APO), and calculate
+      // the other by subtracting it from the total number of operands.
+      for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx)
+        if (getData(OpIdx, Lane).APO)
+          CntTrue++;
+      unsigned CntFalse = NumOperands - CntTrue;
+      return std::max(CntTrue, CntFalse);
+    }
+
+    /// Clears the data.
+    void clear() { OpsVec.clear(); }
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+    LLVM_DUMP_METHOD raw_ostream &print(raw_ostream &OS) {
+      const unsigned Indent = 2;
+      unsigned Cnt = 0;
+      for (const auto &OpDataVec : OpsVec) {
+        OS << Cnt++ << "\n";
+        for (const auto &OpData : OpDataVec) {
+          OS.indent(Indent) << "{";
+          if (Value *V = OpData.V)
+            OS << *V;
+          else
+            OS << "null";
+          OS << ", APO:" << OpData.APO << "}\n";
+        }
+        OS << "\n";
+      }
+      return OS;
+    }
+
+    /// Debug print.
+    LLVM_DUMP_METHOD void dump() {
+      print(dbgs());
+    }
+#endif
+  };
+
 private:
   struct TreeEntry;
 
   /// Checks if all users of \p I are the part of the vectorization tree.
   bool areAllUsersVectorized(Instruction *I) const;
 
   /// \returns the cost of the vectorizable entry.
   int getEntryCost(TreeEntry *E);
private:
 
   /// \returns a vector from a collection of scalars in \p VL.
   Value *Gather(ArrayRef<Value *> VL, VectorType *Ty);
 
   /// \returns whether the VectorizableTree is fully vectorizable and will
   /// be beneficial even the tree height is tiny.
   bool isFullyVectorizableTinyTree();
 
-  /// \reorder commutative operands to get better probability of
+  /// Helper index value for getBestOperand().
+  static const unsigned FailedIdx = UINT_MAX;
+
+  /// Search all operands in Ops[*][Lane] for the operand that matches
+  /// best with the one in Ops[OpIdx][LastLane] and return its index.
+  unsigned getBestOperand(unsigned OpIdx, int Lane, int LastLane,
+                          VLOperands &Ops,
+                          const SmallVectorImpl<OpMode> &Modes);
+
+  /// \reorder the operands in \p Ops to improve vectorization.
+  void reorderOperandVecs(VLOperands &Ops);
+
+  /// \reorder commutative or alt operands to get better probability of
   /// generating vectorized code.
-  void reorderInputsAccordingToOpcode(const InstructionsState &S,
-                                      ArrayRef<Value *> VL,
+  void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
                                       SmallVectorImpl<Value *> &Left,
                                       SmallVectorImpl<Value *> &Right);
   struct TreeEntry {
     TreeEntry(std::vector<TreeEntry> &Container) : Container(Container) {}
 
     /// \returns true if the scalars in VL are equal to this entry.
     bool isSame(ArrayRef<Value *> VL) const {
       if (VL.size() == Scalars.size())
struct TreeEntry {
     /// Does this entry require reordering?
     ArrayRef<unsigned> ReorderIndices;
 
     /// Points back to the VectorizableTree.
     ///
     /// Only used for Graphviz right now.  Unfortunately GraphTrait::NodeRef has
     /// to be a pointer and needs to be able to initialize the child iterator.
     /// Thus we need a reference back to the container to translate the indices
     /// to entries.
     std::vector<TreeEntry> &Container;
 
     /// The TreeEntry index containing the user of this entry.  We can actually
     /// have multiple users so the data structure is not truly a tree.
     SmallVector<EdgeInfo, 1> UserTreeIndices;
 
   private:
     /// The operands of each instruction in each lane Operands[op_index][lane].
     /// Note: This helps avoid the replication of the code that performs the
     /// reordering of operands during buildTree_rec() and vectorizeTree().
     SmallVector<ValueList, 2> Operands;
 
   public:
     /// Set this bundle's \p OpIdx'th operand to \p OpVL.
     void setOperand(unsigned OpIdx, ArrayRef<Value *> OpVL,
                     ArrayRef<unsigned> ReuseShuffleIndices) {
       if (Operands.size() < OpIdx + 1)
         Operands.resize(OpIdx + 1);
       assert(Operands[OpIdx].size() == 0 && "Already resized?");
       Operands[OpIdx].resize(Scalars.size());
       for (unsigned Lane = 0, E = Scalars.size(); Lane != E; ++Lane)
         Operands[OpIdx][Lane] = (!ReuseShuffleIndices.empty())
                                     ? OpVL[ReuseShuffleIndices[Lane]]
                                     : OpVL[Lane];
     }
 
     /// If there is a user TreeEntry, then set its operand.
     void trySetUserTEOperand(const EdgeInfo &UserTreeIdx,
                              ArrayRef<Value *> OpVL,
                              ArrayRef<unsigned> ReuseShuffleIndices) {
       if (UserTreeIdx.Idx >= 0) {
         auto &VectorizableTree = Container;
         VectorizableTree[UserTreeIdx.Idx].setOperand(UserTreeIdx.EdgeIdx, OpVL,
                                                      ReuseShuffleIndices);
       }
     }
 
     /// \returns the \p OpIdx operand of this TreeEntry.
     ValueList &getOperand(unsigned OpIdx) {
       assert(OpIdx < Operands.size() && "Off bounds");
       return Operands[OpIdx];
     }
 
     /// \return the single \p OpIdx operand.
     Value *getSingleOperand(unsigned OpIdx) const {
       assert(OpIdx < Operands.size() && "Off bounds");
       assert(!Operands[OpIdx].empty() && "No operand availabe");
       return Operands[OpIdx][0];
     }
 
 #ifndef NDEBUG
     /// Debug printer.
     LLVM_DUMP_METHOD void dump() const {
       for (unsigned OpI = 0, OpE = Operands.size(); OpI != OpE; ++OpI) {
         dbgs() << "Operand " << OpI << ":\n";
         for (const Value *V : Operands[OpI])
           dbgs().indent(2) << *V << "\n";
       }
       dbgs() << "Scalars: \n";
       for (Value *V : Scalars)
         dbgs().indent(2) << *V << "\n";
       dbgs() << "NeedToGather: " << NeedToGather << "\n";
       dbgs() << "VectorizedValue: ";
       if (VectorizedValue)
         dbgs() << *VectorizedValue;
       else
         dbgs() << "NULL";
       dbgs() << "\n";
       dbgs() << "ReuseShuffleIndices: ";
       if (ReuseShuffleIndices.empty())
         dbgs() << "Emtpy";
       else
         for (unsigned Idx : ReuseShuffleIndices)
           dbgs() << Idx << ", ";
       dbgs() << "\n";
       dbgs() << "ReorderIndices: ";
       for (unsigned Idx : ReorderIndices)
switch (ShuffleOrOp) {
     case Instruction::Xor:
       newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
 
       // Sort operands of the instructions so that each side is more likely to
       // have the same opcode.
       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
         ValueList Left, Right;
-        reorderInputsAccordingToOpcode(S, VL, Left, Right);
+        reorderInputsAccordingToOpcode(VL, Left, Right);
         UserTreeIdx.EdgeIdx = 0;
         buildTree_rec(Left, Depth + 1, UserTreeIdx);
         UserTreeIdx.EdgeIdx = 1;
         buildTree_rec(Right, Depth + 1, UserTreeIdx);
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
case Instruction::ShuffleVector:
         return;
       }
       newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
 
       // Reorder operands if reordering would enable vectorization.
       if (isa<BinaryOperator>(VL0)) {
         ValueList Left, Right;
-        reorderInputsAccordingToOpcode(S, VL, Left, Right);
+        reorderInputsAccordingToOpcode(VL, Left, Right);
         UserTreeIdx.EdgeIdx = 0;
         buildTree_rec(Left, Depth + 1, UserTreeIdx);
         UserTreeIdx.EdgeIdx = 1;
         buildTree_rec(Right, Depth + 1, UserTreeIdx);
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
   for (unsigned I = VL.size(); I > 0; --I) {
     unsigned Idx = I - 1;
     if (!UniqueElements.insert(VL[Idx]).second)
       ShuffledElements.insert(Idx);
   }
   return getGatherCost(VecTy, ShuffledElements);
 }
 
-// Return true if the i'th left and right operands can be commuted.
-//
-// The vectorizer is trying to either have all elements one side being
-// instruction with the same opcode to enable further vectorization, or having
-// a splat to lower the vectorizing cost.
-static bool shouldReorderOperands(int i, ArrayRef<Value *> Left,
-                                  ArrayRef<Value *> Right,
-                                  bool AllSameOpcodeLeft,
-                                  bool AllSameOpcodeRight, bool SplatLeft,
-                                  bool SplatRight) {
-  Value *PrevLeft = Left[i - 1];
-  Value *PrevRight = Right[i - 1];
-  Value *CurrLeft = Left[i];
-  Value *CurrRight = Right[i];
-
-  // If we have "SplatRight", try to see if commuting is needed to preserve it.
-  if (SplatRight) {
-    if (CurrRight == PrevRight)
-      // Preserve SplatRight
-      return false;
-    if (CurrLeft == PrevRight) {
-      // Commuting would preserve SplatRight, but we don't want to break
-      // SplatLeft either, i.e. preserve the original order if possible.
-      // (FIXME: why do we care?)
-      if (SplatLeft && CurrLeft == PrevLeft)
-        return false;
-      return true;
-    }
-  }
-  // Symmetrically handle Right side.
-  if (SplatLeft) {
-    if (CurrLeft == PrevLeft)
-      // Preserve SplatLeft
-      return false;
-    if (CurrRight == PrevLeft)
-      return true;
+// Search all operands in Ops[*][Lane] for the one that matches best
+// Ops[OpIdx][LastLane] and return its opreand index.
+// If no good match can be found, return FailedIdx.
+unsigned BoUpSLP::getBestOperand(unsigned OpIdx, int Lane, int LastLane,
+                                 VLOperands &Ops,
+                                 const SmallVectorImpl<OpMode> &Modes) {
+  unsigned NumOperands = Ops.getNumOperands();
+
+  // The operand of the previous lane at OpIdx.
+  Value *OpLastLane = Ops.getData(OpIdx, LastLane).V;
+
+  // Our strategy mode for OpIdx.
+  OpMode Mode = Modes[OpIdx];
+
+  // The linearized opcode of the operand at OpIdx, Lane.
+  bool OpIdxAPO = Ops.getData(OpIdx, Lane).APO;
+
+  // Iterate through all unused operands.
+  for (unsigned Idx = 0; Idx != NumOperands; ++Idx) {
+    // Get the operand at Idx and Lane.
+    auto &OpData = Ops.getData(Idx, Lane);
+    Value *Op = OpData.V;
+    bool OpAPO = OpData.APO;
+
+    // Skip already selected operands.
+    if (OpData.IsUsed)
+      continue;
+
+    // Skip if we are trying to move the operand to a position with a different
+    // opcode in the linearized tree form. This would break the semantics.
+    if (OpAPO != OpIdxAPO)
+      continue;
+
+    // Look for an operand that matches the current mode.
+    switch (Mode) {
+    case OpMode::Load:
+      if (isa<LoadInst>(Op)) {
+        // Figure out which is left and right, so that we can check for
+        // consecutive loads
+        bool LeftToRight = Lane > LastLane;
+        Value *OpLeft = (LeftToRight) ? OpLastLane : Op;
+        Value *OpRight = (LeftToRight) ? Op : OpLastLane;
+        if (isConsecutiveAccess(cast<LoadInst>(OpLeft), cast<LoadInst>(OpRight),
+                                *DL, *SE)) {
+          OpData.IsUsed = true;
+          return Idx;
+        }
+      }
+      break;
+    case OpMode::Opcode:
+      if (isa<Instruction>(Op))
+        if (cast<Instruction>(Op)->getOpcode() ==
+            cast<Instruction>(OpLastLane)->getOpcode()) {
+          OpData.IsUsed = true;
+          return Idx;
+        }
+      break;
+    case OpMode::Constant:
+      if (isa<Constant>(Op)) {
+        OpData.IsUsed = true;
+        return Idx;
+      }
+      break;
+    case OpMode::Splat: {
+      if (Op == OpLastLane) {
+        OpData.IsUsed = true;
+        return Idx;
+      }
+      break;
+    }
+    case OpMode::Failed:
+      return FailedIdx;
+    }
+   }
+  // If we could not find a good match return FailedIdx.
+  return FailedIdx;
+}
+
+/// Helper for reorderOperandVecs. \Returns the lane that we should start
+/// reordering from. This is the one which has the least number of operands that
+/// can freely move about.
+static unsigned getBestLaneToStartReordering(const BoUpSLP::VLOperands &Ops) {
+  unsigned BestLane = 0;
+  unsigned Min = UINT_MAX;
+  for (unsigned Lane = 0, NumLanes = Ops.getNumLanes(); Lane != NumLanes;
+       ++Lane) {
+    unsigned NumFreeOps = Ops.getMaxNumOperandsThatCanBeReordered(Lane);
+    if (NumFreeOps < Min) {
+      Min = NumFreeOps;
+      BestLane = Lane;
+    }
+  }
+  return BestLane;
+}
+
+// Performs operand reordering for 2 or more operands.
+// The original operands are in OrigOps[OpIdx][Lane].
+// The reordered operands are returned in 'SortedOps[OpIdx][Lane]'.
+void BoUpSLP::reorderOperandVecs(VLOperands &Ops) {
+  unsigned NumOperands = Ops.getNumOperands();
+  unsigned NumLanes = Ops.getNumLanes();
+  // Each operand has its own mode. We are using this mode to help us select the
+  // instructions for each lane, so that they match best with the ones we have
+  // selected so far.
+  SmallVector<OpMode, 2> Modes(NumOperands);
+
+  // This is a greedy single-pass algorithm. We are going over each lane once
+  // and deciding on the best order right away with no back-tracking. However,
+  // in order to increase its effectiveness, we start with the lane that has
+  // operands that can move the least. For example, given the following lanes:
+  //  Lane 0 : A[0] = B[0] + C[0]   // Visited 3rd
+  //  Lane 1 : A[1] = C[1] - B[1]   // Visited 1st
+  //  Lane 2 : A[2] = B[2] + C[2]   // Visited 2nd
+  //  Lane 3 : A[3] = C[3] - B[3]   // Visited 4th
+  // we will start at Lane 1, since the operands of the subtraction cannot be
+  // reordered. Then we will visit the rest of the lanes in a circular fashion.
+  // That is, Lanes 2, then Lane 0, and finally Lane 3.
+
+  // Find the first lane that we will start our search from.
+  unsigned FirstLane = getBestLaneToStartReordering(Ops);
+
+  // Initialize the modes.
+  for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
+    Value *OpLane0 = Ops.getValue(OpIdx, FirstLane);
+    // Keep track if we have instructions with all the same opcode on one side.
+    if (isa<LoadInst>(OpLane0))
+      Modes[OpIdx] = OpMode::Load;
+    else if (isa<Instruction>(OpLane0))
+      Modes[OpIdx] = OpMode::Opcode;
+    else if (isa<Constant>(OpLane0))
+      Modes[OpIdx] = OpMode::Constant;
+    else if (isa<Argument>(OpLane0))
+      // Our best hope is a Splat. It may save some cost in some cases.
+      Modes[OpIdx] = OpMode::Splat;
+    else
+      llvm_unreachable("Bad Operand");
   }
 
-  Instruction *ILeft = dyn_cast<Instruction>(CurrLeft);
-  Instruction *IRight = dyn_cast<Instruction>(CurrRight);
-
-  // If we have "AllSameOpcodeRight", try to see if the left operands preserves
-  // it and not the right, in this case we want to commute.
-  if (AllSameOpcodeRight) {
-    unsigned RightPrevOpcode = cast<Instruction>(PrevRight)->getOpcode();
-    if (IRight && RightPrevOpcode == IRight->getOpcode())
-      // Do not commute, a match on the right preserves AllSameOpcodeRight
-      return false;
-    if (ILeft && RightPrevOpcode == ILeft->getOpcode()) {
-      // We have a match and may want to commute, but first check if there is
-      // not also a match on the existing operands on the Left to preserve
-      // AllSameOpcodeLeft, i.e. preserve the original order if possible.
-      // (FIXME: why do we care?)
-      if (AllSameOpcodeLeft && ILeft &&
-          cast<Instruction>(PrevLeft)->getOpcode() == ILeft->getOpcode())
-        return false;
-      return true;
+  // 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;
+      if (Lane < 0 || Lane >= (int)NumLanes)
+        continue;
+      int LastLane = Lane - Direction;
+      assert(LastLane >= 0 && LastLane < (int)NumLanes && "Out of bounds");
+      // Look for a good match for each operand.
+      for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
+        // Search for the operand that matches SortedOps[OpIdx][Lane-1].
+        unsigned BestIdx = getBestOperand(OpIdx, Lane, LastLane, Ops, Modes);
+        // By not selecting a value, we allow the operands that follow to select
+        // a better matching value. We will get a non-null value in the next run
+        // of getBestOperand().
+        if (BestIdx != FailedIdx)
+          // Swap the current operand with the one returned by getBestOperand().
+          Ops.swap(OpIdx, BestIdx, Lane);
+        else
+          // If we failed to find a best operand, then set the mode to
+          // 'Failed'.
+          Modes[OpIdx] = OpMode::Failed;
       }
     }
-  // Symmetrically handle Left side.
-  if (AllSameOpcodeLeft) {
-    unsigned LeftPrevOpcode = cast<Instruction>(PrevLeft)->getOpcode();
-    if (ILeft && LeftPrevOpcode == ILeft->getOpcode())
-      return false;
-    if (IRight && LeftPrevOpcode == IRight->getOpcode())
-      return true;
   }
-  return false;
 }
 
-void BoUpSLP::reorderInputsAccordingToOpcode(const InstructionsState &S,
-                                             ArrayRef<Value *> VL,
+// Perform operand reordering on the instructions in VL.
+void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
                                              SmallVectorImpl<Value *> &Left,
                                              SmallVectorImpl<Value *> &Right) {
-  assert(!VL.empty() && Left.empty() && Right.empty() &&
-         "Unexpected instruction/operand lists");
-
-  // Push left and right operands of binary operation into Left and Right
-  for (Value *V : VL) {
-    auto *I = cast<Instruction>(V);
-    assert(S.isOpcodeOrAlt(I) && "Incorrect instruction in vector");
-    Left.push_back(I->getOperand(0));
-    Right.push_back(I->getOperand(1));
-  }
-
-  // Keep track if we have instructions with all the same opcode on one side.
-  bool AllSameOpcodeLeft = isa<Instruction>(Left[0]);
-  bool AllSameOpcodeRight = isa<Instruction>(Right[0]);
-  // Keep track if we have one side with all the same value (broadcast).
-  bool SplatLeft = true;
-  bool SplatRight = true;
-
-  for (unsigned i = 1, e = VL.size(); i != e; ++i) {
-    Instruction *I = cast<Instruction>(VL[i]);
-    // Commute to favor either a splat or maximizing having the same opcodes on
-    // one side.
-    if (I->isCommutative() &&
-        shouldReorderOperands(i, Left, Right, AllSameOpcodeLeft,
-                              AllSameOpcodeRight, SplatLeft, SplatRight))
-      std::swap(Left[i], Right[i]);
-
-    // Update Splat* and AllSameOpcode* after the insertion.
-    SplatRight = SplatRight && (Right[i - 1] == Right[i]);
-    SplatLeft = SplatLeft && (Left[i - 1] == Left[i]);
-    AllSameOpcodeLeft = AllSameOpcodeLeft && isa<Instruction>(Left[i]) &&
-                        (cast<Instruction>(Left[i - 1])->getOpcode() ==
-                         cast<Instruction>(Left[i])->getOpcode());
-    AllSameOpcodeRight = AllSameOpcodeRight && isa<Instruction>(Right[i]) &&
-                         (cast<Instruction>(Right[i - 1])->getOpcode() ==
-                          cast<Instruction>(Right[i])->getOpcode());
-  }
-
-  // If one operand end up being broadcast, return this operand order.
-  if (SplatRight || SplatLeft)
+  if (VL.empty())
     return;
-
-  // Finally check if we can get longer vectorizable chain by reordering
-  // without breaking the good operand order detected above.
-  // E.g. If we have something like-
-  // load a[0] - load b[0]
-  // load b[1] + load a[1]
-  // load a[2] - load b[2]
-  // load a[3] + load b[3]
-  // Reordering the second load b[1] + load a[1] would allow us to vectorize
-  // this code and we still retain AllSameOpcode property.
-  // FIXME: This load reordering might break AllSameOpcode in some rare cases
-  // such as-
-  // add a[0],c[0]  load b[0]
-  // add a[1],c[2]  load b[1]
-  // b[2]           load b[2]
-  // add a[3],c[3]  load b[3]
-  for (unsigned j = 0, e = VL.size() - 1; j < e; ++j) {
-    if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
-      if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
-        if (isConsecutiveAccess(L, L1, *DL, *SE)) {
-          auto *VL1 = cast<Instruction>(VL[j]);
-          auto *VL2 = cast<Instruction>(VL[j + 1]);
-          if (VL2->isCommutative()) {
-            std::swap(Left[j + 1], Right[j + 1]);
-            continue;
-          }
-          if (VL1->isCommutative()) {
-            std::swap(Left[j], Right[j]);
-            continue;
-          }
-        }
-      }
-    }
-    if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
-      if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
-        if (isConsecutiveAccess(L, L1, *DL, *SE)) {
-          auto *VL1 = cast<Instruction>(VL[j]);
-          auto *VL2 = cast<Instruction>(VL[j + 1]);
-          if (VL2->isCommutative()) {
-            std::swap(Left[j + 1], Right[j + 1]);
-            continue;
-          }
-          if (VL1->isCommutative()) {
-            std::swap(Left[j], Right[j]);
-            continue;
-          }
-        }
-      }
-    }
-    // else unchanged
-  }
+  VLOperands Ops(VL);
+  // Reorder the operands in place.
+  reorderOperandVecs(Ops);
+  Left = Ops.getVL(0);
+  Right = Ops.getVL(1);
 }
 
 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL,
                                         const InstructionsState &S) {
   // Get the basic block this bundle is in. All instructions in the bundle
   // should be in this block.
   auto *Front = cast<Instruction>(S.OpValue);
   auto *BB = Front->getParent();

test/Transforms/SLPVectorizer/X86/alternate-int.ll

;
   %r5 = insertelement <8 x i32>   %r4, i32 %ab5, i32 5
   %r6 = insertelement <8 x i32>   %r5, i32 %ab6, i32 6
   %r7 = insertelement <8 x i32>   %r6, i32 %ab7, i32 7
   ret <8 x i32> %r7
 }
 
 define <8 x i32> @add_sub_v8i32_splat(<8 x i32> %a, i32 %b) {
 ; CHECK-LABEL: @add_sub_v8i32_splat(
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <8 x i32> [[A:%.*]], <8 x i32> undef, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <4 x i32> undef, i32 [[B:%.*]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <4 x i32> [[TMP2]], <4 x i32> undef, <4 x i32> zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = add <4 x i32> [[TMP1]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <8 x i32> [[A]], <8 x i32> undef, <4 x i32> <i32 4, i32 5, i32 6, i32 7>
-; CHECK-NEXT:    [[TMP6:%.*]] = sub <4 x i32> [[TMP3]], [[TMP5]]
-; CHECK-NEXT:    [[R7:%.*]] = shufflevector <4 x i32> [[TMP4]], <4 x i32> [[TMP6]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <8 x i32> undef, i32 [[B:%.*]], i32 0
+; CHECK-NEXT:    [[TMP2:%.*]] = shufflevector <8 x i32> [[TMP1]], <8 x i32> undef, <8 x i32> zeroinitializer
+; CHECK-NEXT:    [[TMP3:%.*]] = add <8 x i32> [[TMP2]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = sub <8 x i32> [[TMP2]], [[A]]
+; CHECK-NEXT:    [[R7:%.*]] = shufflevector <8 x i32> [[TMP3]], <8 x i32> [[TMP4]], <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 12, i32 13, i32 14, i32 15>
 ; CHECK-NEXT:    ret <8 x i32> [[R7]]
 ;
   %a0 = extractelement <8 x i32> %a, i32 0
   %a1 = extractelement <8 x i32> %a, i32 1
   %a2 = extractelement <8 x i32> %a, i32 2
   %a3 = extractelement <8 x i32> %a, i32 3
   %a4 = extractelement <8 x i32> %a, i32 4
   %a5 = extractelement <8 x i32> %a, i32 5

test/Transforms/SLPVectorizer/X86/crash_lencod.ll

entry:
   %arrayidx156 = getelementptr inbounds [13 x i16], [13 x i16]* undef, i64 0, i64 10
   store i16 %conv153, i16* %arrayidx156, align 4
   ret void
 }
 
 define fastcc void @dct36(double* %inbuf) {
 ; CHECK-LABEL: @dct36(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[ARRAYIDX41:%.*]] = getelementptr inbounds double, double* [[INBUF:%.*]], i64 2
-; CHECK-NEXT:    [[ARRAYIDX44:%.*]] = getelementptr inbounds double, double* [[INBUF]], i64 1
-; CHECK-NEXT:    [[TMP0:%.*]] = load double, double* [[ARRAYIDX44]], align 8
-; CHECK-NEXT:    [[ADD46:%.*]] = fadd double [[TMP0]], undef
-; CHECK-NEXT:    store double [[ADD46]], double* [[ARRAYIDX41]], align 8
-; CHECK-NEXT:    [[TMP1:%.*]] = load double, double* [[INBUF]], align 8
-; CHECK-NEXT:    [[ADD49:%.*]] = fadd double [[TMP1]], [[TMP0]]
-; CHECK-NEXT:    store double [[ADD49]], double* [[ARRAYIDX44]], align 8
+; CHECK-NEXT:    [[ARRAYIDX44:%.*]] = getelementptr inbounds double, double* [[INBUF:%.*]], i64 1
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[INBUF]] to <2 x double>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <2 x double> [[TMP1]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> undef, double [[TMP2]], i32 0
+; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x double> [[TMP3]], double undef, i32 1
+; CHECK-NEXT:    [[TMP5:%.*]] = fadd <2 x double> [[TMP1]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = bitcast double* [[ARRAYIDX44]] to <2 x double>*
+; CHECK-NEXT:    store <2 x double> [[TMP5]], <2 x double>* [[TMP6]], align 8
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %arrayidx41 = getelementptr inbounds double, double* %inbuf, i64 2
   %arrayidx44 = getelementptr inbounds double, double* %inbuf, i64 1
   %0 = load double, double* %arrayidx44, align 8
   %add46 = fadd double %0, undef
   store double %add46, double* %arrayidx41, align 8
   %1 = load double, double* %inbuf, align 8
   %add49 = fadd double %1, %0
   store double %add49, double* %arrayidx44, align 8
   ret void
 }

test/Transforms/SLPVectorizer/X86/crash_smallpt.ll

 ; CHECK-NEXT:    br i1 undef, label [[FOR_BODY42_LR_PH_US:%.*]], label [[_Z5CLAMPD_EXIT_1:%.*]]
 ; CHECK:       cond.false51.us:
 ; CHECK-NEXT:    unreachable
 ; CHECK:       cond.true48.us:
 ; CHECK-NEXT:    br i1 undef, label [[COND_TRUE63_US:%.*]], label [[COND_FALSE66_US:%.*]]
 ; CHECK:       cond.false66.us:
 ; CHECK-NEXT:    [[ADD_I276_US:%.*]] = fadd double 0.000000e+00, undef
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> undef, double [[ADD_I276_US]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> [[TMP0]], double undef, i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = fadd <2 x double> [[TMP1]], <double 0.000000e+00, double 0xBFA5CC2D1960285F>
+; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> [[TMP0]], double 0xBFA5CC2D1960285F, i32 1
+; CHECK-NEXT:    [[TMP2:%.*]] = fadd <2 x double> [[TMP1]], <double 0.000000e+00, double undef>
 ; CHECK-NEXT:    [[TMP3:%.*]] = fmul <2 x double> [[TMP2]], <double 1.400000e+02, double 1.400000e+02>
 ; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP3]], <double 5.000000e+01, double 5.200000e+01>
 ; CHECK-NEXT:    [[TMP5:%.*]] = fmul <2 x double> undef, [[TMP2]]
 ; CHECK-NEXT:    [[TMP6:%.*]] = bitcast double* [[AGG_TMP99208_SROA_0_0_IDX]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP4]], <2 x double>* [[TMP6]], align 8
 ; CHECK-NEXT:    [[TMP7:%.*]] = bitcast double* [[AGG_TMP101211_SROA_0_0_IDX]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP5]], <2 x double>* [[TMP7]], align 8
 ; CHECK-NEXT:    unreachable

test/Transforms/SLPVectorizer/X86/operandorder.ll

 }
 
 define void @shuffle_preserve_broadcast(double * noalias %from,
 ; CHECK-LABEL: @shuffle_preserve_broadcast(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LP:%.*]]
 ; CHECK:       lp:
 ; CHECK-NEXT:    [[P:%.*]] = phi double [ 1.000000e+00, [[LP]] ], [ 0.000000e+00, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[FROM_1:%.*]] = getelementptr double, double* [[FROM:%.*]], i32 1
-; CHECK-NEXT:    [[V0_1:%.*]] = load double, double* [[FROM]], align 4
-; CHECK-NEXT:    [[V0_2:%.*]] = load double, double* [[FROM_1]], align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> undef, double [[V0_1]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x double> [[TMP0]], <2 x double> undef, <2 x i32> zeroinitializer
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[FROM:%.*]] to <2 x double>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[P]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> [[TMP2]], double [[V0_2]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> [[TMP1]], <2 x i32> <i32 0, i32 2>
 ; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP1]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = bitcast double* [[TO:%.*]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP4]], <2 x double>* [[TMP5]], align 4
 ; CHECK-NEXT:    br i1 undef, label [[LP]], label [[EXT:%.*]]
 ; CHECK:       ext:
 ; CHECK-NEXT:    ret void
 ;
   double * noalias %to,
   double %v1, double %v2) {
 entry:
 br label %lp
 

 }
 
 define void @shuffle_preserve_broadcast2(double * noalias %from,
 ; CHECK-LABEL: @shuffle_preserve_broadcast2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LP:%.*]]
 ; CHECK:       lp:
 ; CHECK-NEXT:    [[P:%.*]] = phi double [ 1.000000e+00, [[LP]] ], [ 0.000000e+00, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[FROM_1:%.*]] = getelementptr double, double* [[FROM:%.*]], i32 1
-; CHECK-NEXT:    [[V0_1:%.*]] = load double, double* [[FROM]], align 4
-; CHECK-NEXT:    [[V0_2:%.*]] = load double, double* [[FROM_1]], align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> undef, double [[P]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> [[TMP0]], double [[V0_2]], i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[V0_1]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> undef, <2 x i32> zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[FROM:%.*]] to <2 x double>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[P]], i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> [[TMP1]], <2 x i32> <i32 0, i32 2>
+; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP3]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = bitcast double* [[TO:%.*]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP4]], <2 x double>* [[TMP5]], align 4
 ; CHECK-NEXT:    br i1 undef, label [[LP]], label [[EXT:%.*]]
 ; CHECK:       ext:
 ; CHECK-NEXT:    ret void
 ;
   double * noalias %to,
   double %v1, double %v2) {

 }
 
 define void @shuffle_preserve_broadcast3(double * noalias %from,
 ; CHECK-LABEL: @shuffle_preserve_broadcast3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LP:%.*]]
 ; CHECK:       lp:
 ; CHECK-NEXT:    [[P:%.*]] = phi double [ 1.000000e+00, [[LP]] ], [ 0.000000e+00, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[FROM_1:%.*]] = getelementptr double, double* [[FROM:%.*]], i32 1
-; CHECK-NEXT:    [[V0_1:%.*]] = load double, double* [[FROM]], align 4
-; CHECK-NEXT:    [[V0_2:%.*]] = load double, double* [[FROM_1]], align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> undef, double [[P]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x double> [[TMP0]], double [[V0_2]], i32 1
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[V0_1]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> undef, <2 x i32> zeroinitializer
-; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP1]], [[TMP3]]
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[FROM:%.*]] to <2 x double>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[P]], i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = shufflevector <2 x double> [[TMP2]], <2 x double> [[TMP1]], <2 x i32> <i32 0, i32 2>
+; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP3]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP5:%.*]] = bitcast double* [[TO:%.*]] to <2 x double>*
 ; CHECK-NEXT:    store <2 x double> [[TMP4]], <2 x double>* [[TMP5]], align 4
 ; CHECK-NEXT:    br i1 undef, label [[LP]], label [[EXT:%.*]]
 ; CHECK:       ext:
 ; CHECK-NEXT:    ret void
 ;
   double * noalias %to,
   double %v1, double %v2) {

 }
 
 define void @shuffle_preserve_broadcast5(double * noalias %from,
 ; CHECK-LABEL: @shuffle_preserve_broadcast5(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LP:%.*]]
 ; CHECK:       lp:
 ; CHECK-NEXT:    [[P:%.*]] = phi double [ 1.000000e+00, [[LP]] ], [ 0.000000e+00, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[FROM_1:%.*]] = getelementptr double, double* [[FROM:%.*]], i32 1
-; CHECK-NEXT:    [[V0_1:%.*]] = load double, double* [[FROM]], align 4
-; CHECK-NEXT:    [[V0_2:%.*]] = load double, double* [[FROM_1]], align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x double> undef, double [[V0_1]], i32 0
-; CHECK-NEXT:    [[TMP1:%.*]] = shufflevector <2 x double> [[TMP0]], <2 x double> undef, <2 x i32> zeroinitializer
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <2 x double> undef, double [[V0_2]], i32 0
-; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> [[TMP2]], double [[P]], i32 1
-; CHECK-NEXT:    [[TMP4:%.*]] = fadd <2 x double> [[TMP1]], [[TMP3]]
-; CHECK-NEXT:    [[TMP5:%.*]] = bitcast double* [[TO:%.*]] to <2 x double>*
-; CHECK-NEXT:    store <2 x double> [[TMP4]], <2 x double>* [[TMP5]], align 4
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast double* [[FROM:%.*]] to <2 x double>*
+; CHECK-NEXT:    [[TMP1:%.*]] = load <2 x double>, <2 x double>* [[TMP0]], align 4
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <2 x double> [[TMP1]], i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <2 x double> undef, double [[TMP2]], i32 0
+; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <2 x double> [[TMP3]], double [[P]], i32 1
+; CHECK-NEXT:    [[TMP5:%.*]] = shufflevector <2 x double> [[TMP1]], <2 x double> undef, <2 x i32> <i32 1, i32 0>
+; CHECK-NEXT:    [[TMP6:%.*]] = fadd <2 x double> [[TMP4]], [[TMP5]]
+; CHECK-NEXT:    [[TMP7:%.*]] = bitcast double* [[TO:%.*]] to <2 x double>*
+; CHECK-NEXT:    store <2 x double> [[TMP6]], <2 x double>* [[TMP7]], align 4
 ; CHECK-NEXT:    br i1 undef, label [[LP]], label [[EXT:%.*]]
 ; CHECK:       ext:
 ; CHECK-NEXT:    ret void
 ;
   double * noalias %to,
   double %v1, double %v2) {
 entry:
 br label %lp