[SLP] Allow to duplicate instruction in multiple bundles by introducing pseudo operations.

[dtemirbulatov]

Summary

This is new functionality that allows duplicate(reuse) scalars existing instruction in multiple times in vector operations. This change is a part of D28907.

[RKSimon]

test/Transforms/SLPVectorizer/X86/duplicate.ll

14

This test case is pretty nasty, can you clean it up at all please?

[dtemirbulatov]

update duplicate.ll testcase.

[dtemirbulatov]

This is quite rare cases when it decide to duplicate after limiting to a maximum number of elements of less than half of vector size and calculating cost of this transformation. Abandoning.

lib/Transforms/Vectorize/SLPVectorizer.cpp

 /// meaningful vectorization path such as x86_fp80 and ppc_f128. This just
 /// avoids spending time checking the cost model and realizing that they will
 /// be inevitably scalarized.
 static bool isValidElementType(Type *Ty) {
   return VectorType::isValidElementType(Ty) && !Ty->isX86_FP80Ty() &&
          !Ty->isPPC_FP128Ty();
 }
 
-/// \returns true if all of the instructions in \p VL are in the same block or
-/// false otherwise.
-static bool allSameBlock(ArrayRef<Value *> VL) {
-  Instruction *I0 = dyn_cast<Instruction>(VL[0]);
-  if (!I0)
-    return false;
-  BasicBlock *BB = I0->getParent();
-  for (int i = 1, e = VL.size(); i < e; i++) {
-    Instruction *I = dyn_cast<Instruction>(VL[i]);
-    if (!I)
-      return false;
-
-    if (BB != I->getParent())
-      return false;
-  }
-  return true;
-}
-
-/// \returns True if all of the values in \p VL are constants.
-static bool allConstant(ArrayRef<Value *> VL) {
-  for (Value *i : VL)
-    if (!isa<Constant>(i))
-      return false;
-  return true;
-}
-
-/// \returns True if all of the values in \p VL are identical.
-static bool isSplat(ArrayRef<Value *> VL) {
-  for (unsigned i = 1, e = VL.size(); i < e; ++i)
-    if (VL[i] != VL[0])
-      return false;
-  return true;
-}
-
 /// Checks if the vector of instructions can be represented as a shuffle, like:
 /// %x0 = extractelement <4 x i8> %x, i32 0
 /// %x3 = extractelement <4 x i8> %x, i32 3
 /// %y1 = extractelement <4 x i8> %y, i32 1
 /// %y2 = extractelement <4 x i8> %y, i32 2
 /// %x0x0 = mul i8 %x0, %x0
 /// %x3x3 = mul i8 %x3, %x3
 /// %y1y1 = mul i8 %y1, %y1
struct InstructionsState {
   unsigned getOpcode() const {
     return MainOp ? MainOp->getOpcode() : 0;
   }
 
   unsigned getAltOpcode() const {
     return AltOp ? AltOp->getOpcode() : 0;
   }
 
-  /// Some of the instructions in the list have alternate opcodes.
-  bool isAltShuffle() const { return getOpcode() != getAltOpcode(); }
-
-  bool isOpcodeOrAlt(Instruction *I) const {
-    unsigned CheckedOpcode = I->getOpcode();
-    return getOpcode() == CheckedOpcode || getAltOpcode() == CheckedOpcode;
-  }
-
   InstructionsState() = delete;
   InstructionsState(Value *OpValue, Instruction *MainOp, Instruction *AltOp)
       : OpValue(OpValue), MainOp(MainOp), AltOp(AltOp) {}
 };
 
-} // end anonymous namespace
+class InstructionOrPseudo {
+private:
+  /// Parent of the operation.
+  Value *Parent;
+  /// The operation instance.
+  Value *Op;
+  /// Instruction represantation of the operation.
+  Instruction *OpInst;
+  /// Pseudo operation after replacement.
+  Instruction *PseudoOp = nullptr;
+
+public:
+  /// Main operation in a group of operations.
+  Instruction *MainOp = nullptr;
+  /// Alternative operation in a group of operations.
+  Instruction *AltOp = nullptr;
+  /// Main opcode of a group of operations.
+  unsigned MainOpcode = 0;
+  /// Alternative opcode of a group of operations.
+  unsigned AltOpcode = 0;
 
-/// Chooses the correct key for scheduling data. If \p Op has the same (or
-/// alternate) opcode as \p OpValue, the key is \p Op. Otherwise the key is \p
-/// OpValue.
-static Value *isOneOf(const InstructionsState &S, Value *Op) {
-  auto *I = dyn_cast<Instruction>(Op);
-  if (I && S.isOpcodeOrAlt(I))
+  InstructionOrPseudo(Value *Parent, Value *Op) : Parent(Parent), Op(Op) {
+    OpInst = dyn_cast<Instruction>(Op);
+  }
+
+  /// Set properties of this operation after analysis of a group of operations.
+  void setInstructionsState(const InstructionsState &S) {
+    MainOp = S.MainOp;
+    AltOp = S.AltOp;
+    if (MainOp)
+      MainOpcode = MainOp->getOpcode();
+    if (AltOp)
+      AltOpcode = AltOp->getOpcode();
+  }
+
+  /// Replace pseudo opration with real one.
+  void replaceWith(Instruction *NewOp) {
+    PseudoOp = OpInst;
+    Op = NewOp;
+    OpInst = NewOp;
+  }
+
+  bool isPseudoEqual(Value *V) {
+    if (!PseudoOp)
+      return false;
+    if (PseudoOp == V)
+      return true;
+    return false;
+  }
+
+  bool isPseudo() {
+    if (PseudoOp)
+      return true;
+    return false;
+  }
+
+  bool isEqual(InstructionOrPseudo *IOP) {
+    return ((Op == IOP->getOp()) || isPseudoEqual(IOP->getOp()) ||
+            IOP->isPseudoEqual(Op));
+  }
+
+  /// Returns parent of this operation
+  Value* getParent() {
+    return Parent;
+  }
+
+  /// Returns a Value represntation of this operation.
+  Value* getOp() {
     return Op;
-  return S.OpValue;
   }
 
-/// \returns analysis of the Instructions in \p VL described in
+  /// Returns an Instruction represntation of this operation.
+  Instruction* getOpInst() {
+    return OpInst;
+  }
+
+  bool isAltShuffle() const {
+    return (MainOpcode != 0 && AltOpcode != 0 && MainOpcode != AltOpcode);
+  }
+
+  bool isOpcodeOrAlt() const {
+    unsigned CheckedOpcode = OpInst->getOpcode();
+    return MainOpcode == CheckedOpcode || AltOpcode == CheckedOpcode;
+  }
+
+  std::pair<Value *, unsigned> getKey() const {
+    assert(Parent && "Incorrect parent!");
+    return std::make_pair(Parent, MainOpcode);
+  }
+};
+} // end anonymous namespace
+
+/// \returns True if all of the values in \p IL are constants.
+static bool allConstant(ArrayRef<InstructionOrPseudo *> IL) {
+  return llvm::all_of(
+      make_range(IL.begin(), IL.end()),
+      [](InstructionOrPseudo *I) -> bool { return isa<Constant>(I->getOp()); });
+}
+
+/// \returns True if all of the values in \p IL are identical.
+static bool isSplat(ArrayRef<InstructionOrPseudo *> IL) {
+  return llvm::all_of(make_range(IL.begin(), IL.end()),
+                      [&](InstructionOrPseudo *I) -> bool {
+                        return I->getOp() == IL[0]->getOp();
+                      });
+}
+
+/// \returns true if all of the instructions in \p IL are in the same block or
+/// false otherwise.
+static bool allSameBlock(ArrayRef<InstructionOrPseudo *> IL) {
+  if (!IL[0]->getOpInst())
+    return false;
+  BasicBlock *BB = IL[0]->getOpInst()->getParent();
+  for (int i = 1, e = IL.size(); i < e; i++) {
+    if (!IL[i]->getOpInst())
+      return false;
+
+    if (BB != IL[i]->getOpInst()->getParent())
+      return false;
+  }
+  return true;
+}
+
+/// \returns analysis of the Instructions in \p IL described in
 /// InstructionsState, the Opcode that we suppose the whole list
 /// could be vectorized even if its structure is diverse.
-static InstructionsState getSameOpcode(ArrayRef<Value *> VL,
+static InstructionsState getSameOpcode(ArrayRef<InstructionOrPseudo *> IL,
                                        unsigned BaseIndex = 0) {
   // Make sure these are all Instructions.
-  if (llvm::any_of(VL, [](Value *V) { return !isa<Instruction>(V); }))
-    return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+  if (llvm::any_of(IL, [](InstructionOrPseudo *IOP) { return !IOP->getOpInst(); }))
+    return InstructionsState(IL[BaseIndex]->getOp(), nullptr, nullptr);
 
-  bool IsCastOp = isa<CastInst>(VL[BaseIndex]);
-  bool IsBinOp = isa<BinaryOperator>(VL[BaseIndex]);
-  unsigned Opcode = cast<Instruction>(VL[BaseIndex])->getOpcode();
+  Instruction* BaseOp = IL[BaseIndex]->getOpInst();
+  bool IsCastOp = isa<CastInst>(BaseOp);
+  bool IsBinOp = isa<BinaryOperator>(BaseOp);
+  unsigned Opcode = BaseOp->getOpcode();
   unsigned AltOpcode = Opcode;
   unsigned AltIndex = BaseIndex;
 
   // Check for one alternate opcode from another BinaryOperator.
   // TODO - generalize to support all operators (types, calls etc.).
-  for (int Cnt = 0, E = VL.size(); Cnt < E; Cnt++) {
-    unsigned InstOpcode = cast<Instruction>(VL[Cnt])->getOpcode();
-    if (IsBinOp && isa<BinaryOperator>(VL[Cnt])) {
+  for (int Cnt = 0, E = IL.size(); Cnt < E; Cnt++) {
+    auto *I = IL[Cnt]->getOpInst();
+    unsigned InstOpcode = I->getOpcode();
+    if (IsBinOp && isa<BinaryOperator>(I)) {
       if (InstOpcode == Opcode || InstOpcode == AltOpcode)
         continue;
       if (Opcode == AltOpcode) {
         AltOpcode = InstOpcode;
         AltIndex = Cnt;
         continue;
       }
-    } else if (IsCastOp && isa<CastInst>(VL[Cnt])) {
-      Type *Ty0 = cast<Instruction>(VL[BaseIndex])->getOperand(0)->getType();
-      Type *Ty1 = cast<Instruction>(VL[Cnt])->getOperand(0)->getType();
+    } else if (IsCastOp && isa<CastInst>(I)) {
+      Type *Ty0 = BaseOp->getOperand(0)->getType();
+      Type *Ty1 = I->getOperand(0)->getType();
       if (Ty0 == Ty1) {
         if (InstOpcode == Opcode || InstOpcode == AltOpcode)
           continue;
         if (Opcode == AltOpcode) {
           AltOpcode = InstOpcode;
           AltIndex = Cnt;
           continue;
         }
       }
     } else if (InstOpcode == Opcode || InstOpcode == AltOpcode)
       continue;
-    return InstructionsState(VL[BaseIndex], nullptr, nullptr);
+    return InstructionsState(BaseOp, nullptr, nullptr);
   }
 
-  return InstructionsState(VL[BaseIndex], cast<Instruction>(VL[BaseIndex]),
-                           cast<Instruction>(VL[AltIndex]));
+  return InstructionsState(BaseOp, BaseOp, IL[AltIndex]->getOpInst());
 }
 
 /// \returns true if all of the values in \p VL have the same type or false
 /// otherwise.
 static bool allSameType(ArrayRef<Value *> VL) {
   Type *Ty = VL[0]->getType();
-  for (int i = 1, e = VL.size(); i < e; i++)
-    if (VL[i]->getType() != Ty)
-      return false;
-
-  return true;
+  return llvm::all_of(
+      make_range(VL.begin(), VL.end()),
+      [&](Value *V) -> bool { return V->getType() == Ty; });
 }
 
 /// \returns True if Extract{Value,Element} instruction extracts element Idx.
 static Optional<unsigned> getExtractIndex(Instruction *E) {
   unsigned Opcode = E->getOpcode();
   assert((Opcode == Instruction::ExtractElement ||
           Opcode == Instruction::ExtractValue) &&
          "Expected extractelement or extractvalue instruction.");

 
 /// Bottom Up SLP Vectorizer.
 class BoUpSLP {
 public:
   using ValueList = SmallVector<Value *, 8>;
   using InstrList = SmallVector<Instruction *, 16>;
   using ValueSet = SmallPtrSet<Value *, 16>;
   using StoreList = SmallVector<StoreInst *, 8>;
+  using IOPList = SmallVector<InstructionOrPseudo *, 8>;
   using ExtraValueToDebugLocsMap =
       MapVector<Value *, SmallVector<Instruction *, 2>>;
 
   BoUpSLP(Function *Func, ScalarEvolution *Se, TargetTransformInfo *Tti,
           TargetLibraryInfo *TLi, AliasAnalysis *Aa, LoopInfo *Li,
           DominatorTree *Dt, AssumptionCache *AC, DemandedBits *DB,
           const DataLayout *DL, OptimizationRemarkEmitter *ORE)
       : F(Func), SE(Se), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt), AC(AC),
public:
   /// into account (anf updating it, if required) list of externally used
   /// values stored in \p ExternallyUsedValues.
   void buildTree(ArrayRef<Value *> Roots,
                  ExtraValueToDebugLocsMap &ExternallyUsedValues,
                  ArrayRef<Value *> UserIgnoreLst = None);
 
   /// Clear the internal data structures that are created by 'buildTree'.
   void deleteTree() {
+    InstructionOrPseudoArray.clear();
     VectorizableTree.clear();
     ScalarToTreeEntry.clear();
     MustGather.clear();
     ExternalUses.clear();
     NumOpsWantToKeepOrder.clear();
     NumOpsWantToKeepOriginalOrder = 0;
     for (auto &Iter : BlocksSchedules) {
       BlockScheduling *BS = Iter.second.get();
private:
 
   /// 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);
 
   /// This is the recursive part of buildTree.
-  void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth, int);
+  void buildTree_rec(Value *Parent, ArrayRef<Value *> Roots, unsigned Depth, int);
 
-  /// \returns true if the ExtractElement/ExtractValue instructions in \p VL can
+  /// \returns true if the ExtractElement/ExtractValue instructions in \p IL can
   /// be vectorized to use the original vector (or aggregate "bitcast" to a
   /// vector) and sets \p CurrentOrder to the identity permutation; otherwise
   /// returns false, setting \p CurrentOrder to either an empty vector or a
   /// non-identity permutation that allows to reuse extract instructions.
-  bool canReuseExtract(ArrayRef<Value *> VL, Value *OpValue,
+  bool canReuseExtract(ArrayRef<InstructionOrPseudo *> IL,
                        SmallVectorImpl<unsigned> &CurrentOrder) const;
 
   /// Vectorize a single entry in the tree.
   Value *vectorizeTree(TreeEntry *E);
 
   /// Vectorize a single entry in the tree, starting in \p VL.
-  Value *vectorizeTree(ArrayRef<Value *> VL);
+  Value *vectorizeTree(Value *Parent, ArrayRef<Value *> VL);
 
   /// \returns the scalarization cost for this type. Scalarization in this
   /// context means the creation of vectors from a group of scalars.
   int getGatherCost(Type *Ty, const DenseSet<unsigned> &ShuffledIndices);
 
   /// \returns the scalarization cost for this list of values. Assuming that
   /// this subtree gets vectorized, we may need to extract the values from the
   /// roots. This method calculates the cost of extracting the values.
-  int getGatherCost(ArrayRef<Value *> VL);
+  int getGatherCost(ArrayRef<InstructionOrPseudo *> IL);
 
   /// Set the Builder insert point to one after the last instruction in
   /// the bundle
-  void setInsertPointAfterBundle(ArrayRef<Value *> VL,
-                                 const InstructionsState &S);
+  void setInsertPointAfterBundle(ArrayRef<InstructionOrPseudo *> IL);
 
-  /// \returns a vector from a collection of scalars in \p VL.
-  Value *Gather(ArrayRef<Value *> VL, VectorType *Ty);
+  /// \returns a vector from a collection of scalars in \p IL.
+  Value *Gather(ArrayRef<InstructionOrPseudo *> IL, VectorType *Ty);
 
   /// \returns whether the VectorizableTree is fully vectorizable and will
   /// be beneficial even the tree height is tiny.
   bool isFullyVectorizableTinyTree();
 
+  Instruction *propagateMetadata(Instruction *I,
+                                 ArrayRef<InstructionOrPseudo *> IL);
+
+  void propagateIRFlags(Value *I,
+                        ArrayRef<InstructionOrPseudo *> IL,
+                        Value *OpValue);
+
   /// \reorder commutative operands in alt shuffle if they result in
   ///  vectorized code.
-  void reorderAltShuffleOperands(const InstructionsState &S,
-                                 ArrayRef<Value *> VL,
+  void reorderAltShuffleOperands(ArrayRef<InstructionOrPseudo *> IL,
                                  SmallVectorImpl<Value *> &Left,
                                  SmallVectorImpl<Value *> &Right);
 
   /// \reorder commutative operands to get better probability of
   /// generating vectorized code.
-  void reorderInputsAccordingToOpcode(unsigned Opcode, ArrayRef<Value *> VL,
+  void reorderInputsAccordingToOpcode(ArrayRef<InstructionOrPseudo *> IL,
                                       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())
-        return std::equal(VL.begin(), VL.end(), Scalars.begin());
-      return VL.size() == ReuseShuffleIndices.size() &&
+    /// \returns true if the scalars in IL are equal to this entry.
+    bool isSame(ArrayRef<InstructionOrPseudo *> IL) const {
+      if (IL.size() == Scalars.size())
+        return std::equal(IL.begin(), IL.end(), Scalars.begin(),
+               [this](InstructionOrPseudo *I1, InstructionOrPseudo *I2)
+                     { return I1->isEqual(I2); });
+      return IL.size() == ReuseShuffleIndices.size() &&
              std::equal(
-                 VL.begin(), VL.end(), ReuseShuffleIndices.begin(),
-                 [this](Value *V, unsigned Idx) { return V == Scalars[Idx]; });
+                 IL.begin(), IL.end(), ReuseShuffleIndices.begin(),
+                 [this](InstructionOrPseudo *I1, unsigned Idx)
+                 { return I1->isEqual(Scalars[Idx]); });
     }
 
     /// A vector of scalars.
-    ValueList Scalars;
+    IOPList Scalars;
 
     /// The Scalars are vectorized into this value. It is initialized to Null.
     Value *VectorizedValue = nullptr;
 
     /// Do we need to gather this sequence ?
     bool NeedToGather = false;
 
     /// Does this sequence require some shuffling?
struct TreeEntry {
     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<int, 1> UserTreeIndices;
   };
 
   /// Create a new VectorizableTree entry.
-  void newTreeEntry(ArrayRef<Value *> VL, bool Vectorized, int &UserTreeIdx,
+  void newTreeEntry(ArrayRef<InstructionOrPseudo *> IL, bool Vectorized,
+                    int &UserTreeIdx,
                     ArrayRef<unsigned> ReuseShuffleIndices = None,
                     ArrayRef<unsigned> ReorderIndices = None) {
     VectorizableTree.emplace_back(VectorizableTree);
     int idx = VectorizableTree.size() - 1;
     TreeEntry *Last = &VectorizableTree[idx];
-    Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
+    Last->Scalars.insert(Last->Scalars.begin(), IL.begin(), IL.end());
     Last->NeedToGather = !Vectorized;
     Last->ReuseShuffleIndices.append(ReuseShuffleIndices.begin(),
                                      ReuseShuffleIndices.end());
     Last->ReorderIndices = ReorderIndices;
     if (Vectorized) {
-      for (int i = 0, e = VL.size(); i != e; ++i) {
-        assert(!getTreeEntry(VL[i]) && "Scalar already in tree!");
-        ScalarToTreeEntry[VL[i]] = idx;
+      for (InstructionOrPseudo *IOP : IL) {
+        auto *I = IOP->getOpInst();
+        assert(
+            (ScalarToTreeEntry.find(I) == ScalarToTreeEntry.end() ||
+             ScalarToTreeEntry[I].find(IOP->getKey()) ==
+                 ScalarToTreeEntry[I].end()) &&
+            "Scalar already in tree!");
+        ScalarToTreeEntry[I][IOP->getKey()] = idx;
       }
     } else {
-      MustGather.insert(VL.begin(), VL.end());
+      for (InstructionOrPseudo *IOP : IL)
+        MustGather.insert(IOP->getOp());
     }
 
     if (UserTreeIdx >= 0)
       Last->UserTreeIndices.push_back(UserTreeIdx);
     UserTreeIdx = idx;
   }
 
   /// -- Vectorization State --
   /// Holds all of the tree entries.
   std::vector<TreeEntry> VectorizableTree;
 
   TreeEntry *getTreeEntry(Value *V) {
-    auto I = ScalarToTreeEntry.find(V);
-    if (I != ScalarToTreeEntry.end())
-      return &VectorizableTree[I->second];
+    auto *I = dyn_cast<Instruction>(V);
+    if (!I)
+      return nullptr;
+    auto It = ScalarToTreeEntry.find(I);
+    if (It != ScalarToTreeEntry.end()) {
+      auto &STT = It->second;
+      for (auto STTI : STT)
+        for (auto *IOP : VectorizableTree[STTI.second].Scalars)
+          if (IOP->getOpInst() == I)
+            return &VectorizableTree[STTI.second];
+    }
     return nullptr;
   }
 
+  std::vector<std::unique_ptr<InstructionOrPseudo>> InstructionOrPseudoArray;
+
+  /// Allocates InstructionOrPseudo.
+  InstructionOrPseudo *allocInstructionOrPseudo(Value* Parent, Value *V) {
+    InstructionOrPseudoArray.emplace_back(
+                       llvm::make_unique<InstructionOrPseudo>(Parent, V));
+    int idx = InstructionOrPseudoArray.size() - 1;
+    return (InstructionOrPseudoArray[idx]).get();
+  }
+
   /// Maps a specific scalar to its tree entry.
-  SmallDenseMap<Value*, int> ScalarToTreeEntry;
+  SmallDenseMap<Instruction *, SmallDenseMap<std::pair<Value *, unsigned>, int>>
+      ScalarToTreeEntry;
 
   /// A list of scalars that we found that we need to keep as scalars.
   ValueSet MustGather;
 
   /// This POD struct describes one external user in the vectorized tree.
   struct ExternalUser {
     ExternalUser(Value *S, llvm::User *U, int L)
         : Scalar(S), User(U), Lane(L) {}
private:
   /// vector instruction).
   struct ScheduleData {
     // The initial value for the dependency counters. It means that the
     // dependencies are not calculated yet.
     enum { InvalidDeps = -1 };
 
     ScheduleData() = default;
 
-    void init(int BlockSchedulingRegionID, Value *OpVal) {
+    void init(int BlockSchedulingRegionID) {
       FirstInBundle = this;
       NextInBundle = nullptr;
       NextLoadStore = nullptr;
       IsScheduled = false;
+      Parent = nullptr;
+      Opcode = 0;
+      IsPseudo = false;
+      SchedulingRegionID = BlockSchedulingRegionID;
+      UnscheduledDepsInBundle = UnscheduledDeps;
+      clearDependencies();
+    }
+
+    // Initialize ScheduleData for pseudo instruction
+    // with ScheduleData for an original instruction OpOrigin.
+    void init(int BlockSchedulingRegionID, ScheduleData *OpOrigin,
+              InstructionOrPseudo *IOP) {
+      FirstInBundle = this;
+      NextInBundle = nullptr;
+      IsScheduled = false;
+      Parent = IOP->getParent();
+      Opcode = IOP->MainOpcode;
+      IsPseudo = true;
+      Inst = OpOrigin->Inst;
+      NextLoadStore = OpOrigin->NextLoadStore;
       SchedulingRegionID = BlockSchedulingRegionID;
       UnscheduledDepsInBundle = UnscheduledDeps;
       clearDependencies();
-      OpValue = OpVal;
     }
 
     /// Returns true if the dependency information has been calculated.
     bool hasValidDependencies() const { return Dependencies != InvalidDeps; }
 
     /// Returns true for single instructions and for bundle representatives
     /// (= the head of a bundle).
     bool isSchedulingEntity() const { return FirstInBundle == this; }
struct ScheduleData {
     /// The sum of UnscheduledDeps in a bundle. Equals to UnscheduledDeps for
     /// single instructions.
     int UnscheduledDepsInBundle = InvalidDeps;
 
     /// True if this instruction is scheduled (or considered as scheduled in the
     /// dry-run).
     bool IsScheduled = false;
 
-    /// Opcode of the current instruction in the schedule data.
-    Value *OpValue = nullptr;
+    /// Opcode that represents instructions to be vectorized.
+    unsigned Opcode = 0;
+
+    /// Parent of this operation.
+    Value *Parent = nullptr;
+
+    /// True if this is a pseudo operation.
+    bool IsPseudo = false;
   };
 
 #ifndef NDEBUG
   friend inline raw_ostream &operator<<(raw_ostream &os,
                                         const BoUpSLP::ScheduleData &SD) {
     SD.dump(os);
     return os;
   }
void clear() {
         ScheduleRegionSizeLimit = MinScheduleRegionSize;
       ScheduleRegionSize = 0;
 
       // Make a new scheduling region, i.e. all existing ScheduleData is not
       // in the new region yet.
       ++SchedulingRegionID;
     }
 
-    ScheduleData *getScheduleData(Value *V) {
-      ScheduleData *SD = ScheduleDataMap[V];
-      if (SD && SD->SchedulingRegionID == SchedulingRegionID)
+    ScheduleData *getScheduleData(InstructionOrPseudo *IOP) {
+      std::pair<Value *, unsigned> Key = IOP->getKey();
+      auto *I = IOP->getOpInst();
+      ScheduleData *SD = ScheduleDataMap[I][std::make_pair(nullptr, 0)];
+      if (SD && SD->Parent == Key.first && SD->Opcode == Key.second &&
+          SD->SchedulingRegionID == SchedulingRegionID)
         return SD;
-      return nullptr;
-    }
-
-    ScheduleData *getScheduleData(Value *V, Value *Key) {
-      if (V == Key)
-        return getScheduleData(V);
-      auto I = ExtraScheduleDataMap.find(V);
-      if (I != ExtraScheduleDataMap.end()) {
-        ScheduleData *SD = I->second[Key];
-        if (SD && SD->SchedulingRegionID == SchedulingRegionID)
-          return SD;
-      }
+      SD = ScheduleDataMap[I][Key];
+      if (SD && SD->Parent == Key.first && SD->Opcode == Key.second &&
+          SD->SchedulingRegionID == SchedulingRegionID)
       return nullptr;
     }
 
     bool isInSchedulingRegion(ScheduleData *SD) {
       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) {
       SD->IsScheduled = true;
       LLVM_DEBUG(dbgs() << "SLP:   schedule " << *SD << "\n");
 
       ScheduleData *BundleMember = SD;
+      unsigned Opcode = BundleMember->Opcode;
+      Value *Parent = BundleMember->Parent;
       while (BundleMember) {
-        if (BundleMember->Inst != BundleMember->OpValue) {
-          BundleMember = BundleMember->NextInBundle;
-          continue;
-        }
+        assert(BundleMember->Opcode == Opcode &&
+               BundleMember->Parent == Parent && "Corrupt bundle member");
         // Handle the def-use chain dependencies.
         for (Use &U : BundleMember->Inst->operands()) {
           auto *I = dyn_cast<Instruction>(U.get());
           if (!I)
             continue;
           doForAllOpcodes(I, [&ReadyList](ScheduleData *OpDef) {
-            if (OpDef && OpDef->hasValidDependencies() &&
+            if (OpDef->hasValidDependencies() &&
                 OpDef->incrementUnscheduledDeps(-1) == 0) {
               // There are no more unscheduled dependencies after
               // decrementing, so we can put the dependent instruction
               // into the ready list.
               ScheduleData *DepBundle = OpDef->FirstInBundle;
               assert(!DepBundle->IsScheduled &&
                      "already scheduled bundle gets ready");
               ReadyList.insert(DepBundle);
void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
             LLVM_DEBUG(dbgs()
                        << "SLP:    gets ready (mem): " << *DepBundle << "\n");
           }
         }
         BundleMember = BundleMember->NextInBundle;
       }
     }
 
-    void doForAllOpcodes(Value *V,
+    void doForAllOpcodes(Instruction *I,
                          function_ref<void(ScheduleData *SD)> Action) {
-      if (ScheduleData *SD = getScheduleData(V))
+      if (ScheduleDataMap.find(I) == ScheduleDataMap.end())
+        return;
+      for (auto It : ScheduleDataMap[I]) {
+        auto *SD = It.second;
+        if (SD && isInSchedulingRegion(SD))
           Action(SD);
-      auto I = ExtraScheduleDataMap.find(V);
-      if (I != ExtraScheduleDataMap.end())
-        for (auto &P : I->second)
-          if (P.second->SchedulingRegionID == SchedulingRegionID)
-            Action(P.second);
+      }
     }
 
     /// Put all instructions into the ReadyList which are ready for scheduling.
     template <typename ReadyListType>
     void initialFillReadyList(ReadyListType &ReadyList) {
       for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
         doForAllOpcodes(I, [&](ScheduleData *SD) {
           if (SD->isSchedulingEntity() && SD->isReady()) {
             ReadyList.insert(SD);
             LLVM_DEBUG(dbgs()
                        << "SLP:    initially in ready list: " << *I << "\n");
           }
         });
       }
     }
 
     /// Checks if a bundle of instructions can be scheduled, i.e. has no
     /// cyclic dependencies. This is only a dry-run, no instructions are
     /// actually moved at this stage.
-    bool tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
-                           const InstructionsState &S);
+    bool tryScheduleBundle(ArrayRef<InstructionOrPseudo *> IL, BoUpSLP *SLP);
 
     /// Un-bundles a group of instructions.
-    void cancelScheduling(ArrayRef<Value *> VL, Value *OpValue);
+    void cancelScheduling(InstructionOrPseudo *IOP);
 
     /// 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.
-    bool extendSchedulingRegion(Value *V, const InstructionsState &S);
+    bool extendSchedulingRegion(InstructionOrPseudo *IOP);
 
     /// Initialize the ScheduleData structures for new instructions in the
     /// scheduling region.
     void initScheduleData(Instruction *FromI, Instruction *ToI,
                           ScheduleData *PrevLoadStore,
                           ScheduleData *NextLoadStore);
 
     /// Updates the dependency information of a bundle and of all instructions/
struct BlockScheduling {
     int ChunkSize;
 
     /// The allocator position in the current chunk, which is the last entry
     /// of ScheduleDataChunks.
     int ChunkPos;
 
     /// Attaches ScheduleData to Instruction.
     /// Note that the mapping survives during all vectorization iterations, i.e.
-    /// ScheduleData structures are recycled.
-    DenseMap<Value *, ScheduleData *> ScheduleDataMap;
-
-    /// Attaches ScheduleData to Instruction with the leading key.
-    DenseMap<Value *, SmallDenseMap<Value *, ScheduleData *>>
-        ExtraScheduleDataMap;
+    /// ScheduleData structures are recycled. All real instructions are placed
+    /// in [Instruction *][nullptr][0].
+    DenseMap<Instruction *,
+             SmallDenseMap<std::pair<Value *, unsigned>, ScheduleData *>>
+        ScheduleDataMap;
 
     struct ReadyList : SmallVector<ScheduleData *, 8> {
       void insert(ScheduleData *SD) { push_back(SD); }
     };
 
     /// The ready-list for scheduling (only used for the dry-run).
     ReadyList ReadyInsts;
 
struct BlockScheduling {
     // Make sure that the initial SchedulingRegionID is greater than the
     // initial SchedulingRegionID in ScheduleData (which is 0).
     int SchedulingRegionID = 1;
   };
 
   /// Attaches the BlockScheduling structures to basic blocks.
   MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
 
+  /// Remove or subsititude any pseudo instructions in the tree.
+  void eliminatePseudos(BlockScheduling *BS);
+
   /// Performs the "real" scheduling. Done before vectorization is actually
   /// performed in a basic block.
   void scheduleBlock(BlockScheduling *BS);
 
   /// List of users to ignore during scheduling and that don't need extracting.
   ArrayRef<Value *> UserIgnoreList;
 
   using OrdersType = SmallVector<unsigned, 4>;
template <> struct DOTGraphTraits<BoUpSLP *> : public DefaultDOTGraphTraits {
   using TreeEntry = BoUpSLP::TreeEntry;
 
   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
 
   std::string getNodeLabel(const TreeEntry *Entry, const BoUpSLP *R) {
     std::string Str;
     raw_string_ostream OS(Str);
     if (isSplat(Entry->Scalars)) {
-      OS << "<splat> " << *Entry->Scalars[0];
+      OS << "<splat> " << *Entry->Scalars[0]->getOp();
       return Str;
     }
-    for (auto V : Entry->Scalars) {
+    for (auto *IOP : Entry->Scalars) {
+      Value *V = IOP->getOp();
       OS << *V;
-      if (std::any_of(
-              R->ExternalUses.begin(), R->ExternalUses.end(),
-              [&](const BoUpSLP::ExternalUser &EU) { return EU.Scalar == V; }))
+      if (std::any_of(R->ExternalUses.begin(), R->ExternalUses.end(),
+                      [&](const BoUpSLP::ExternalUser &EU) {
+                        return EU.Scalar == V;
+                      }))
         OS << " <extract>";
       OS << "\n";
     }
     return Str;
   }
 
   static std::string getNodeAttributes(const TreeEntry *Entry,
                                        const BoUpSLP *) {

 
 void BoUpSLP::buildTree(ArrayRef<Value *> Roots,
                         ExtraValueToDebugLocsMap &ExternallyUsedValues,
                         ArrayRef<Value *> UserIgnoreLst) {
   deleteTree();
   UserIgnoreList = UserIgnoreLst;
   if (!allSameType(Roots))
     return;
-  buildTree_rec(Roots, 0, -1);
+  buildTree_rec(Roots[0], Roots, 0, -1);
 
   // Collect the values that we need to extract from the tree.
   for (TreeEntry &EIdx : VectorizableTree) {
     TreeEntry *Entry = &EIdx;
 
     // No need to handle users of gathered values.
     if (Entry->NeedToGather)
       continue;
 
     // For each lane:
     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
-      Value *Scalar = Entry->Scalars[Lane];
+      auto *Scalar = Entry->Scalars[Lane];
       int FoundLane = Lane;
       if (!Entry->ReuseShuffleIndices.empty()) {
         FoundLane =
             std::distance(Entry->ReuseShuffleIndices.begin(),
                           llvm::find(Entry->ReuseShuffleIndices, FoundLane));
       }
 
       // Check if the scalar is externally used as an extra arg.
-      auto ExtI = ExternallyUsedValues.find(Scalar);
+      Value *V = Scalar->getOp();
+      auto ExtI = ExternallyUsedValues.find(V);
       if (ExtI != ExternallyUsedValues.end()) {
         LLVM_DEBUG(dbgs() << "SLP: Need to extract: Extra arg from lane "
-                          << Lane << " from " << *Scalar << ".\n");
-        ExternalUses.emplace_back(Scalar, nullptr, FoundLane);
+                          << Lane << " from " << *V << ".\n");
+        ExternalUses.emplace_back(V, nullptr, FoundLane);
       }
-      for (User *U : Scalar->users()) {
+      for (User *U : V->users()) {
         LLVM_DEBUG(dbgs() << "SLP: Checking user:" << *U << ".\n");
 
         Instruction *UserInst = dyn_cast<Instruction>(U);
         if (!UserInst)
           continue;
 
         // Skip in-tree scalars that become vectors
-        if (TreeEntry *UseEntry = getTreeEntry(U)) {
-          Value *UseScalar = UseEntry->Scalars[0];
+        if (TreeEntry *UseEntry = getTreeEntry(UserInst)) {
+          Value *UseScalar = UseEntry->Scalars[0]->getOp();
           // Some in-tree scalars will remain as scalar in vectorized
           // instructions. If that is the case, the one in Lane 0 will
           // be used.
           if (UseScalar != U ||
-              !InTreeUserNeedToExtract(Scalar, UserInst, TLI)) {
+              !InTreeUserNeedToExtract(V, UserInst, TLI)) {
             LLVM_DEBUG(dbgs() << "SLP: \tInternal user will be removed:" << *U
                               << ".\n");
             assert(!UseEntry->NeedToGather && "Bad state");
             continue;
           }
         }
 
         // Ignore users in the user ignore list.
         if (is_contained(UserIgnoreList, UserInst))
           continue;
 
         LLVM_DEBUG(dbgs() << "SLP: Need to extract:" << *U << " from lane "
-                          << Lane << " from " << *Scalar << ".\n");
-        ExternalUses.push_back(ExternalUser(Scalar, U, FoundLane));
+                          << Lane << " from " << *V << ".\n");
+        ExternalUses.push_back(ExternalUser(V, U, FoundLane));
       }
     }
   }
 }
 
-void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
+void BoUpSLP::buildTree_rec(Value *Parent, ArrayRef<Value *> VL, unsigned Depth,
                             int UserTreeIdx) {
-  assert((allConstant(VL) || allSameType(VL)) && "Invalid types!");
+  SmallVector<InstructionOrPseudo *, 4> IL;
+  for (Value *V: VL)
+    IL.push_back(allocInstructionOrPseudo(Parent, V));
+  InstructionsState S = getSameOpcode(IL);
+  for (InstructionOrPseudo *IOP : IL)
+    IOP->setInstructionsState(S);
+
+  assert((allConstant(IL) || allSameType(VL)) && "Invalid types!");
 
-  InstructionsState S = getSameOpcode(VL);
   if (Depth == RecursionMaxDepth) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
-    newTreeEntry(VL, false, UserTreeIdx);
+    newTreeEntry(IL, false, UserTreeIdx);
     return;
   }
 
   // Don't handle vectors.
   if (S.OpValue->getType()->isVectorTy()) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
-    newTreeEntry(VL, false, UserTreeIdx);
+    newTreeEntry(IL, false, UserTreeIdx);
     return;
   }
 
   if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
     if (SI->getValueOperand()->getType()->isVectorTy()) {
       LLVM_DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
+      newTreeEntry(IL, false, UserTreeIdx);
       return;
     }
 
   // If all of the operands are identical or constant we have a simple solution.
-  if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !S.getOpcode()) {
+  if (allConstant(IL) || isSplat(IL) || !allSameBlock(IL) || !S.getOpcode()) {
     LLVM_DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
-    newTreeEntry(VL, false, UserTreeIdx);
+    newTreeEntry(IL, false, UserTreeIdx);
     return;
   }
 
   // We now know that this is a vector of instructions of the same type from
   // the same block.
 
   // Don't vectorize ephemeral values.
-  for (unsigned i = 0, e = VL.size(); i != e; ++i) {
-    if (EphValues.count(VL[i])) {
-      LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *VL[i]
+  for (auto *IOP : IL) {
+    if (EphValues.count(IOP->getOp())) {
+      LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *IOP->getOp()
                         << ") is ephemeral.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
+      newTreeEntry(IL, false, UserTreeIdx);
       return;
     }
   }
 
   // Check if this is a duplicate of another entry.
-  if (TreeEntry *E = getTreeEntry(S.OpValue)) {
-    LLVM_DEBUG(dbgs() << "SLP: \tChecking bundle: " << *S.OpValue << ".\n");
-    if (!E->isSame(VL)) {
-      LLVM_DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
-      return;
-    }
+  TreeEntry *E = getTreeEntry(IL[0]->MainOp);
+  if (E && E->isSame(IL)) {
+    LLVM_DEBUG(dbgs() << "SLP: \tChecking bundle: "
+                      << *IL[0]->MainOp << ".\n");
     // Record the reuse of the tree node.  FIXME, currently this is only used to
     // properly draw the graph rather than for the actual vectorization.
     E->UserTreeIndices.push_back(UserTreeIdx);
-    LLVM_DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *S.OpValue
+    LLVM_DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *IL[0]->MainOp
                       << ".\n");
     return;
   }
 
   // Check that none of the instructions in the bundle are already in the tree.
-  for (unsigned i = 0, e = VL.size(); i != e; ++i) {
-    auto *I = dyn_cast<Instruction>(VL[i]);
-    if (!I)
-      continue;
-    if (getTreeEntry(I)) {
-      LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *VL[i]
+  for (auto *IOP : IL) {
+    auto *I = IOP->getOpInst();
+    // Avoid any non-binary duplicate operation.
+    if ((getTreeEntry(I) && (!isa<BinaryOperator>(I) || IL[0]->MainOp == I)) ||
+        (ScalarToTreeEntry.find(I) != ScalarToTreeEntry.end() &&
+         ScalarToTreeEntry[I].find(IOP->getKey()) !=
+         ScalarToTreeEntry[I].end())) {
+      LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *I
                         << ") is already in tree.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
+      newTreeEntry(IL, false, UserTreeIdx);
       return;
     }
   }
 
   // If any of the scalars is marked as a value that needs to stay scalar, then
   // we need to gather the scalars.
   // The reduction nodes (stored in UserIgnoreList) also should stay scalar.
-  for (unsigned i = 0, e = VL.size(); i != e; ++i) {
-    if (MustGather.count(VL[i]) || is_contained(UserIgnoreList, VL[i])) {
+  for (auto *IOP : IL) {
+    if (MustGather.count(IOP->getOp()) ||
+        is_contained(UserIgnoreList, IOP->getOp())) {
       LLVM_DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
+      newTreeEntry(IL, false, UserTreeIdx);
       return;
     }
   }
 
   // Check that all of the users of the scalars that we want to vectorize are
   // schedulable.
-  auto *VL0 = cast<Instruction>(S.OpValue);
+  auto *VL0 = IL[0]->MainOp;
   BasicBlock *BB = VL0->getParent();
 
   if (!DT->isReachableFromEntry(BB)) {
     // Don't go into unreachable blocks. They may contain instructions with
     // dependency cycles which confuse the final scheduling.
     LLVM_DEBUG(dbgs() << "SLP: bundle in unreachable block.\n");
-    newTreeEntry(VL, false, UserTreeIdx);
+    newTreeEntry(IL, false, UserTreeIdx);
     return;
   }
 
   // Check that every instruction appears once in this bundle.
   SmallVector<unsigned, 4> ReuseShuffleIndicies;
-  SmallVector<Value *, 4> UniqueValues;
+  SmallVector<InstructionOrPseudo *, 4> UniqueValues;
   DenseMap<Value *, unsigned> UniquePositions;
-  for (Value *V : VL) {
+  for (auto *I : IL) {
+    Value *V = I->getOp();
     auto Res = UniquePositions.try_emplace(V, UniqueValues.size());
     ReuseShuffleIndicies.emplace_back(Res.first->second);
-    if (Res.second)
-      UniqueValues.emplace_back(V);
+    if (Res.second) {
+      InstructionOrPseudo *IOP = allocInstructionOrPseudo(Parent, V);
+      IOP->setInstructionsState(S);
+      UniqueValues.emplace_back(IOP);
+    }
   }
-  if (UniqueValues.size() == VL.size()) {
+  if (UniqueValues.size() == IL.size()) {
     ReuseShuffleIndicies.clear();
   } else {
     LLVM_DEBUG(dbgs() << "SLP: Shuffle for reused scalars.\n");
     if (UniqueValues.size() <= 1 || !llvm::isPowerOf2_32(UniqueValues.size())) {
       LLVM_DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
-      newTreeEntry(VL, false, UserTreeIdx);
+      newTreeEntry(IL, false, UserTreeIdx);
       return;
     }
-    VL = UniqueValues;
+    IL = UniqueValues;
   }
 
   auto &BSRef = BlocksSchedules[BB];
   if (!BSRef)
     BSRef = llvm::make_unique<BlockScheduling>(BB);
 
   BlockScheduling &BS = *BSRef.get();
 
-  if (!BS.tryScheduleBundle(VL, this, S)) {
+  if (!BS.tryScheduleBundle(IL, this)) {
     LLVM_DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
-    assert((!BS.getScheduleData(VL0) ||
-            !BS.getScheduleData(VL0)->isPartOfBundle()) &&
+    assert((!BS.getScheduleData(IL[0]) ||
+            !BS.getScheduleData(IL[0])->isPartOfBundle()) &&
            "tryScheduleBundle should cancelScheduling on failure");
-    newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+    newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
     return;
   }
   LLVM_DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
 
-  unsigned ShuffleOrOp = S.isAltShuffle() ?
-                (unsigned) Instruction::ShuffleVector : S.getOpcode();
+  unsigned ShuffleOrOp = IL[0]->isAltShuffle() ?
+                (unsigned) Instruction::ShuffleVector : IL[0]->MainOpcode;
   switch (ShuffleOrOp) {
     case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
 
       // Check for terminator values (e.g. invoke).
-      for (unsigned j = 0; j < VL.size(); ++j)
+      for (unsigned j = 0; j < IL.size(); ++j)
         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
           Instruction *Term = dyn_cast<Instruction>(
-              cast<PHINode>(VL[j])->getIncomingValueForBlock(
+              cast<PHINode>(IL[j]->getOp())->getIncomingValueForBlock(
                   PH->getIncomingBlock(i)));
           if (Term && Term->isTerminator()) {
             LLVM_DEBUG(dbgs()
                        << "SLP: Need to swizzle PHINodes (terminator use).\n");
-            BS.cancelScheduling(VL, VL0);
-            newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+            BS.cancelScheduling(IL[0]);
+            newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
             return;
           }
         }
 
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
 
       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<PHINode>(j)->getIncomingValueForBlock(
+        for (auto *j : IL)
+          Operands.push_back(cast<PHINode>(
+                                 j->getOp())->getIncomingValueForBlock(
                                  PH->getIncomingBlock(i)));
-
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::ExtractValue:
     case Instruction::ExtractElement: {
       OrdersType CurrentOrder;
-      bool Reuse = canReuseExtract(VL, VL0, CurrentOrder);
+      bool Reuse = canReuseExtract(IL, CurrentOrder);
       if (Reuse) {
         LLVM_DEBUG(dbgs() << "SLP: Reusing or shuffling extract sequence.\n");
         ++NumOpsWantToKeepOriginalOrder;
-        newTreeEntry(VL, /*Vectorized=*/true, UserTreeIdx,
+        newTreeEntry(IL, /*Vectorized=*/true, UserTreeIdx,
                      ReuseShuffleIndicies);
         return;
       }
       if (!CurrentOrder.empty()) {
         LLVM_DEBUG({
           dbgs() << "SLP: Reusing or shuffling of reordered extract sequence "
                     "with order";
           for (unsigned Idx : CurrentOrder)
             dbgs() << " " << Idx;
           dbgs() << "\n";
         });
         // Insert new order with initial value 0, if it does not exist,
         // otherwise return the iterator to the existing one.
         auto StoredCurrentOrderAndNum =
             NumOpsWantToKeepOrder.try_emplace(CurrentOrder).first;
         ++StoredCurrentOrderAndNum->getSecond();
-        newTreeEntry(VL, /*Vectorized=*/true, UserTreeIdx, ReuseShuffleIndicies,
+        newTreeEntry(IL, /*Vectorized=*/true, UserTreeIdx, ReuseShuffleIndicies,
                      StoredCurrentOrderAndNum->getFirst());
         return;
       }
       LLVM_DEBUG(dbgs() << "SLP: Gather extract sequence.\n");
-      newTreeEntry(VL, /*Vectorized=*/false, UserTreeIdx, ReuseShuffleIndicies);
-      BS.cancelScheduling(VL, VL0);
+      newTreeEntry(IL, /*Vectorized=*/false, UserTreeIdx, ReuseShuffleIndicies);
+      BS.cancelScheduling(IL[0]);
       return;
     }
     case Instruction::Load: {
       // Check that a vectorized load would load the same memory as a scalar
       // load. For example, we don't want to vectorize loads that are smaller
       // than 8-bit. Even though we have a packed struct {<i2, i2, i2, i2>} LLVM
       // treats loading/storing it as an i8 struct. If we vectorize loads/stores
       // from such a struct, we read/write packed bits disagreeing with the
       // unvectorized version.
       Type *ScalarTy = VL0->getType();
 
       if (DL->getTypeSizeInBits(ScalarTy) !=
           DL->getTypeAllocSizeInBits(ScalarTy)) {
-        BS.cancelScheduling(VL, VL0);
-        newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+        BS.cancelScheduling(IL[0]);
+        newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
         LLVM_DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n");
         return;
       }
 
       // Make sure all loads in the bundle are simple - we can't vectorize
       // atomic or volatile loads.
-      SmallVector<Value *, 4> PointerOps(VL.size());
+      SmallVector<Value *, 4> PointerOps(IL.size());
       auto POIter = PointerOps.begin();
-      for (Value *V : VL) {
-        auto *L = cast<LoadInst>(V);
+      for (auto *I : IL) {
+        auto *L = cast<LoadInst>(I->getOpInst());
         if (!L->isSimple()) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n");
           return;
         }
         *POIter = L->getPointerOperand();
         ++POIter;
       }
 
       OrdersType CurrentOrder;
case Instruction::Load: {
           PtrN = PointerOps[CurrentOrder.back()];
         }
         const SCEV *Scev0 = SE->getSCEV(Ptr0);
         const SCEV *ScevN = SE->getSCEV(PtrN);
         const auto *Diff =
             dyn_cast<SCEVConstant>(SE->getMinusSCEV(ScevN, Scev0));
         uint64_t Size = DL->getTypeAllocSize(ScalarTy);
         // Check that the sorted loads are consecutive.
-        if (Diff && Diff->getAPInt().getZExtValue() == (VL.size() - 1) * Size) {
+        if (Diff && Diff->getAPInt().getZExtValue() == (IL.size() - 1) * Size) {
           if (CurrentOrder.empty()) {
             // Original loads are consecutive and does not require reordering.
             ++NumOpsWantToKeepOriginalOrder;
-            newTreeEntry(VL, /*Vectorized=*/true, UserTreeIdx,
+            newTreeEntry(IL, /*Vectorized=*/true, UserTreeIdx,
                          ReuseShuffleIndicies);
             LLVM_DEBUG(dbgs() << "SLP: added a vector of loads.\n");
           } else {
             // Need to reorder.
             auto I = NumOpsWantToKeepOrder.try_emplace(CurrentOrder).first;
             ++I->getSecond();
-            newTreeEntry(VL, /*Vectorized=*/true, UserTreeIdx,
+            newTreeEntry(IL, /*Vectorized=*/true, UserTreeIdx,
                          ReuseShuffleIndicies, I->getFirst());
             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled loads.\n");
           }
           return;
         }
       }
 
       LLVM_DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
-      BS.cancelScheduling(VL, VL0);
-      newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+      BS.cancelScheduling(IL[0]);
+      newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
       return;
     }
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::SIToFP:
     case Instruction::UIToFP:
     case Instruction::Trunc:
     case Instruction::FPTrunc:
     case Instruction::BitCast: {
       Type *SrcTy = VL0->getOperand(0)->getType();
-      for (unsigned i = 0; i < VL.size(); ++i) {
-        Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
+      for (auto *IOP : IL) {
+        Type *Ty = IOP->getOpInst()->getOperand(0)->getType();
         if (Ty != SrcTy || !isValidElementType(Ty)) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs()
                      << "SLP: Gathering casts with different src types.\n");
           return;
         }
       }
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of casts.\n");
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
+        for (auto *I : IL)
+          Operands.push_back(I->getOpInst()->getOperand(i));
 
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::ICmp:
     case Instruction::FCmp: {
       // Check that all of the compares have the same predicate.
       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
       Type *ComparedTy = VL0->getOperand(0)->getType();
-      for (unsigned i = 1, e = VL.size(); i < e; ++i) {
-        CmpInst *Cmp = cast<CmpInst>(VL[i]);
+      for (auto *IOP : IL) {
+        CmpInst *Cmp = cast<CmpInst>(IOP->getOpInst());
         if (Cmp->getPredicate() != P0 ||
             Cmp->getOperand(0)->getType() != ComparedTy) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs()
                      << "SLP: Gathering cmp with different predicate.\n");
           return;
         }
       }
 
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
+        for (auto *I : IL)
+          Operands.push_back(I->getOpInst()->getOperand(i));
 
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::Select:
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
     case Instruction::UDiv:
     case Instruction::SDiv:
     case Instruction::FDiv:
     case Instruction::URem:
     case Instruction::SRem:
     case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, 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.getOpcode(), VL, Left, Right);
-        buildTree_rec(Left, Depth + 1, UserTreeIdx);
-        buildTree_rec(Right, Depth + 1, UserTreeIdx);
+        reorderInputsAccordingToOpcode(IL, Left, Right);
+        buildTree_rec(VL0, Left, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Right, Depth + 1, UserTreeIdx);
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
+        for (auto *Inst: IL)
+          Operands.push_back(Inst->getOpInst()->getOperand(i));
 
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
 
     case Instruction::GetElementPtr: {
       // We don't combine GEPs with complicated (nested) indexing.
-      for (unsigned j = 0; j < VL.size(); ++j) {
-        if (cast<Instruction>(VL[j])->getNumOperands() != 2) {
+      for (auto *IOP : IL) {
+        if (IOP->getOpInst()->getNumOperands() != 2) {
           LLVM_DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           return;
         }
       }
 
       // We can't combine several GEPs into one vector if they operate on
       // different types.
       Type *Ty0 = VL0->getOperand(0)->getType();
-      for (unsigned j = 0; j < VL.size(); ++j) {
-        Type *CurTy = cast<Instruction>(VL[j])->getOperand(0)->getType();
+      for (auto *IOP : IL) {
+        Type *CurTy = IOP->getOpInst()->getOperand(0)->getType();
         if (Ty0 != CurTy) {
           LLVM_DEBUG(dbgs()
                      << "SLP: not-vectorizable GEP (different types).\n");
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           return;
         }
       }
 
       // We don't combine GEPs with non-constant indexes.
-      for (unsigned j = 0; j < VL.size(); ++j) {
-        auto Op = cast<Instruction>(VL[j])->getOperand(1);
+      for (auto *IOP : IL) {
+        auto Op = IOP->getOpInst()->getOperand(1);
         if (!isa<ConstantInt>(Op)) {
           LLVM_DEBUG(dbgs()
                      << "SLP: not-vectorizable GEP (non-constant indexes).\n");
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           return;
         }
       }
 
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of GEPs.\n");
       for (unsigned i = 0, e = 2; i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
+        for (auto *j : IL)
+          Operands.push_back(j->getOpInst()->getOperand(i));
 
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::Store: {
       // Check if the stores are consecutive or of we need to swizzle them.
-      for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
-        if (!isConsecutiveAccess(VL[i], VL[i + 1], *DL, *SE)) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+      for (unsigned i = 0, e = IL.size() - 1; i < e; ++i)
+        if (!isConsecutiveAccess(IL[i]->getOp(), IL[i + 1]->getOp(),
+                                 *DL, *SE)) {
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
           return;
         }
 
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of stores.\n");
 
       ValueList Operands;
-      for (Value *j : VL)
-        Operands.push_back(cast<Instruction>(j)->getOperand(0));
+      for (auto *j : IL)
+        Operands.push_back(j->getOpInst()->getOperand(0));
 
-      buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+      buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       return;
     }
     case Instruction::Call: {
       // Check if the calls are all to the same vectorizable intrinsic.
       CallInst *CI = cast<CallInst>(VL0);
       // Check if this is an Intrinsic call or something that can be
       // represented by an intrinsic call
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
       if (!isTriviallyVectorizable(ID)) {
-        BS.cancelScheduling(VL, VL0);
-        newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+        BS.cancelScheduling(IL[0]);
+        newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
         LLVM_DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
         return;
       }
       Function *Int = CI->getCalledFunction();
       Value *A1I = nullptr;
       if (hasVectorInstrinsicScalarOpd(ID, 1))
         A1I = CI->getArgOperand(1);
-      for (unsigned i = 1, e = VL.size(); i != e; ++i) {
-        CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
+      for (unsigned i = 1, e = IL.size(); i != e; ++i) {
+        CallInst *CI2 = dyn_cast<CallInst>(IL[i]->getOpInst());
         if (!CI2 || CI2->getCalledFunction() != Int ||
             getVectorIntrinsicIDForCall(CI2, TLI) != ID ||
             !CI->hasIdenticalOperandBundleSchema(*CI2)) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
-          LLVM_DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i]
-                            << "\n");
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
+          LLVM_DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" <<
+                            *IL[i]->getOp() << "\n");
           return;
         }
         // ctlz,cttz and powi are special intrinsics whose second argument
         // should be same in order for them to be vectorized.
         if (hasVectorInstrinsicScalarOpd(ID, 1)) {
           Value *A1J = CI2->getArgOperand(1);
           if (A1I != A1J) {
-            BS.cancelScheduling(VL, VL0);
-            newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+            BS.cancelScheduling(IL[0]);
+            newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
             LLVM_DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI
                               << " argument " << A1I << "!=" << A1J << "\n");
             return;
           }
         }
         // Verify that the bundle operands are identical between the two calls.
         if (CI->hasOperandBundles() &&
             !std::equal(CI->op_begin() + CI->getBundleOperandsStartIndex(),
                         CI->op_begin() + CI->getBundleOperandsEndIndex(),
                         CI2->op_begin() + CI2->getBundleOperandsStartIndex())) {
-          BS.cancelScheduling(VL, VL0);
-          newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+          BS.cancelScheduling(IL[0]);
+          newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
           LLVM_DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:"
-                            << *CI << "!=" << *VL[i] << '\n');
+                            << *CI << "!=" << *IL[i]->getOp() << '\n');
           return;
         }
       }
 
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, true, UserTreeIdx, ReuseShuffleIndicies);
       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL) {
-          CallInst *CI2 = dyn_cast<CallInst>(j);
+        for (auto *VecOp : IL) {
+          CallInst *CI2 = dyn_cast<CallInst>(VecOp->getOpInst());
           Operands.push_back(CI2->getArgOperand(i));
         }
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
     }
     case Instruction::ShuffleVector:
       // If this is not an alternate sequence of opcode like add-sub
       // then do not vectorize this instruction.
-      if (!S.isAltShuffle()) {
-        BS.cancelScheduling(VL, VL0);
-        newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+      if (!IL[0]->isAltShuffle()) {
+        BS.cancelScheduling(IL[0]);
+        newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
         LLVM_DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
         return;
       }
-      newTreeEntry(VL, true, UserTreeIdx, ReuseShuffleIndicies);
+      newTreeEntry(IL, 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;
-        reorderAltShuffleOperands(S, VL, Left, Right);
-        buildTree_rec(Left, Depth + 1, UserTreeIdx);
-        buildTree_rec(Right, Depth + 1, UserTreeIdx);
+        reorderAltShuffleOperands(IL, Left, Right);
+        buildTree_rec(VL0, Left, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Right, Depth + 1, UserTreeIdx);
         return;
       }
 
       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
         ValueList Operands;
         // Prepare the operand vector.
-        for (Value *j : VL)
-          Operands.push_back(cast<Instruction>(j)->getOperand(i));
+        for (auto *VecOp : IL)
+          Operands.push_back(VecOp->getOpInst()->getOperand(i));
 
-        buildTree_rec(Operands, Depth + 1, UserTreeIdx);
+        buildTree_rec(VL0, Operands, Depth + 1, UserTreeIdx);
       }
       return;
 
     default:
-      BS.cancelScheduling(VL, VL0);
-      newTreeEntry(VL, false, UserTreeIdx, ReuseShuffleIndicies);
+      BS.cancelScheduling(IL[0]);
+      newTreeEntry(IL, false, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
       return;
   }
 }
 
 unsigned BoUpSLP::canMapToVector(Type *T, const DataLayout &DL) const {
   unsigned N;
   Type *EltTy;
if (ST) {
     // Check that struct is homogeneous.
     for (const auto *Ty : ST->elements())
       if (Ty != EltTy)
         return 0;
   }
   return N;
 }
 
-bool BoUpSLP::canReuseExtract(ArrayRef<Value *> VL, Value *OpValue,
+bool BoUpSLP::canReuseExtract(ArrayRef<InstructionOrPseudo *> IL,
                               SmallVectorImpl<unsigned> &CurrentOrder) const {
-  Instruction *E0 = cast<Instruction>(OpValue);
+  Instruction *E0 = IL[0]->MainOp;
   assert(E0->getOpcode() == Instruction::ExtractElement ||
          E0->getOpcode() == Instruction::ExtractValue);
-  assert(E0->getOpcode() == getSameOpcode(VL).getOpcode() && "Invalid opcode");
+  assert(E0->getOpcode() == getSameOpcode(IL).getOpcode() && "Invalid opcode");
   // Check if all of the extracts come from the same vector and from the
   // correct offset.
   Value *Vec = E0->getOperand(0);
 
   CurrentOrder.clear();
 
   // We have to extract from a vector/aggregate with the same number of elements.
   unsigned NElts;
   if (E0->getOpcode() == Instruction::ExtractValue) {
     const DataLayout &DL = E0->getModule()->getDataLayout();
     NElts = canMapToVector(Vec->getType(), DL);
     if (!NElts)
       return false;
     // Check if load can be rewritten as load of vector.
     LoadInst *LI = dyn_cast<LoadInst>(Vec);
-    if (!LI || !LI->isSimple() || !LI->hasNUses(VL.size()))
+    if (!LI || !LI->isSimple() || !LI->hasNUses(IL.size()))
       return false;
   } else {
     NElts = Vec->getType()->getVectorNumElements();
   }
 
-  if (NElts != VL.size())
+  if (NElts != IL.size())
     return false;
 
   // Check that all of the indices extract from the correct offset.
   bool ShouldKeepOrder = true;
-  unsigned E = VL.size();
+  unsigned E = IL.size();
   // Assign to all items the initial value E + 1 so we can check if the extract
   // instruction index was used already.
   // Also, later we can check that all the indices are used and we have a
   // consecutive access in the extract instructions, by checking that no
   // element of CurrentOrder still has value E + 1.
   CurrentOrder.assign(E, E + 1);
   unsigned I = 0;
   for (; I < E; ++I) {
-    auto *Inst = cast<Instruction>(VL[I]);
+    auto *Inst = IL[I]->getOpInst();
     if (Inst->getOperand(0) != Vec)
       break;
     Optional<unsigned> Idx = getExtractIndex(Inst);
     if (!Idx)
       break;
     const unsigned ExtIdx = *Idx;
     if (ExtIdx != I) {
       if (ExtIdx >= E || CurrentOrder[ExtIdx] != E + 1)
         break;
       ShouldKeepOrder = false;
+      ShouldKeepOrder = false;
       CurrentOrder[ExtIdx] = I;
     } else {
       if (CurrentOrder[I] != E + 1)
         break;
       CurrentOrder[I] = I;
     }
   }
   if (I < E) {
     CurrentOrder.clear();
     return false;
   }
 
   return ShouldKeepOrder;
 }
 
 bool BoUpSLP::areAllUsersVectorized(Instruction *I) const {
   return I->hasOneUse() ||
          std::all_of(I->user_begin(), I->user_end(), [this](User *U) {
-           return ScalarToTreeEntry.count(U) > 0;
+           return ScalarToTreeEntry.count(dyn_cast<Instruction>(U)) > 0;
          });
 }
 
 int BoUpSLP::getEntryCost(TreeEntry *E) {
-  ArrayRef<Value*> VL = E->Scalars;
+  ArrayRef<InstructionOrPseudo *> IL = E->Scalars;
+  Value *V = E->Scalars[0]->getOp();
 
-  Type *ScalarTy = VL[0]->getType();
-  if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
+  Type *ScalarTy = V->getType();
+  if (StoreInst *SI = dyn_cast<StoreInst>(V))
     ScalarTy = SI->getValueOperand()->getType();
-  else if (CmpInst *CI = dyn_cast<CmpInst>(VL[0]))
+  else if (CmpInst *CI = dyn_cast<CmpInst>(V))
     ScalarTy = CI->getOperand(0)->getType();
-  VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
+  VectorType *VecTy = VectorType::get(ScalarTy, IL.size());
 
   // If we have computed a smaller type for the expression, update VecTy so
   // that the costs will be accurate.
-  if (MinBWs.count(VL[0]))
+  if (MinBWs.count(V))
     VecTy = VectorType::get(
-        IntegerType::get(F->getContext(), MinBWs[VL[0]].first), VL.size());
+        IntegerType::get(F->getContext(), MinBWs[V].first), IL.size());
 
   unsigned ReuseShuffleNumbers = E->ReuseShuffleIndices.size();
   bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();
   int ReuseShuffleCost = 0;
   if (NeedToShuffleReuses) {
     ReuseShuffleCost =
         TTI->getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
   }
   if (E->NeedToGather) {
-    if (allConstant(VL))
+    if (allConstant(IL))
       return 0;
-    if (isSplat(VL)) {
+    if (isSplat(IL)) {
       return ReuseShuffleCost +
              TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
     }
-    if (getSameOpcode(VL).getOpcode() == Instruction::ExtractElement &&
-        allSameType(VL) && allSameBlock(VL)) {
+    if (IL[0]->MainOpcode == Instruction::ExtractElement && allSameBlock(IL)) {
+      ValueList VL;
+      for (auto *IOP : IL)
+        VL.push_back(IOP->getOp());
       Optional<TargetTransformInfo::ShuffleKind> ShuffleKind = isShuffle(VL);
       if (ShuffleKind.hasValue()) {
         int Cost = TTI->getShuffleCost(ShuffleKind.getValue(), VecTy);
-        for (auto *V : VL) {
+        for (auto *IOP : IL) {
           // If all users of instruction are going to be vectorized and this
           // instruction itself is not going to be vectorized, consider this
           // instruction as dead and remove its cost from the final cost of the
           // vectorized tree.
-          if (areAllUsersVectorized(cast<Instruction>(V)) &&
-              !ScalarToTreeEntry.count(V)) {
+          auto *I = IOP->getOpInst();
+          if (areAllUsersVectorized(I) &&
+              !ScalarToTreeEntry.count(I)) {
             auto *IO = cast<ConstantInt>(
-                cast<ExtractElementInst>(V)->getIndexOperand());
+                cast<ExtractElementInst>(I)->getIndexOperand());
             Cost -= TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy,
                                             IO->getZExtValue());
           }
         }
         return ReuseShuffleCost + Cost;
       }
     }
-    return ReuseShuffleCost + getGatherCost(VL);
+    return ReuseShuffleCost + getGatherCost(IL);
   }
-  InstructionsState S = getSameOpcode(VL);
-  assert(S.getOpcode() && allSameType(VL) && allSameBlock(VL) && "Invalid VL");
-  Instruction *VL0 = cast<Instruction>(S.OpValue);
-  unsigned ShuffleOrOp = S.isAltShuffle() ?
-               (unsigned) Instruction::ShuffleVector : S.getOpcode();
+  auto *VL0 = E->Scalars[0]->MainOp;
+  assert(IL[0]->MainOpcode != 0 && allSameBlock(IL) && "Invalid IL");
+  unsigned ShuffleOrOp = IL[0]->isAltShuffle() ?
+             (unsigned) Instruction::ShuffleVector : IL[0]->MainOpcode;
   switch (ShuffleOrOp) {
     case Instruction::PHI:
       return 0;
 
     case Instruction::ExtractValue:
     case Instruction::ExtractElement:
       if (NeedToShuffleReuses) {
         unsigned Idx = 0;
         for (unsigned I : E->ReuseShuffleIndices) {
+          auto *Inst = IL[I]->getOpInst();
           if (ShuffleOrOp == Instruction::ExtractElement) {
             auto *IO = cast<ConstantInt>(
-                cast<ExtractElementInst>(VL[I])->getIndexOperand());
+                cast<ExtractElementInst>(Inst)->getIndexOperand());
             Idx = IO->getZExtValue();
             ReuseShuffleCost -= TTI->getVectorInstrCost(
                 Instruction::ExtractElement, VecTy, Idx);
           } else {
             ReuseShuffleCost -= TTI->getVectorInstrCost(
                 Instruction::ExtractElement, VecTy, Idx);
             ++Idx;
           }
         }
         Idx = ReuseShuffleNumbers;
-        for (Value *V : VL) {
+        for (auto *IOP : IL) {
           if (ShuffleOrOp == Instruction::ExtractElement) {
             auto *IO = cast<ConstantInt>(
-                cast<ExtractElementInst>(V)->getIndexOperand());
+                cast<ExtractElementInst>(IOP->getOpInst())->getIndexOperand());
             Idx = IO->getZExtValue();
           } else {
             --Idx;
           }
           ReuseShuffleCost +=
               TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, Idx);
         }
       }
       if (!E->NeedToGather) {
         int DeadCost = ReuseShuffleCost;
         if (!E->ReorderIndices.empty()) {
           // TODO: Merge this shuffle with the ReuseShuffleCost.
           DeadCost += TTI->getShuffleCost(
               TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
         }
-        for (unsigned i = 0, e = VL.size(); i < e; ++i) {
-          Instruction *E = cast<Instruction>(VL[i]);
+        for (unsigned i = 0, e = IL.size(); i < e; ++i) {
           // If all users are going to be vectorized, instruction can be
           // considered as dead.
           // The same, if have only one user, it will be vectorized for sure.
+          auto *E = IL[i]->getOpInst();
           if (areAllUsersVectorized(E)) {
             // Take credit for instruction that will become dead.
             if (E->hasOneUse()) {
               Instruction *Ext = E->user_back();
               if ((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
                   all_of(Ext->users(),
                          [](User *U) { return isa<GetElementPtrInst>(U); })) {
                 // Use getExtractWithExtendCost() to calculate the cost of
                 // extractelement/ext pair.
                 DeadCost -= TTI->getExtractWithExtendCost(
                     Ext->getOpcode(), Ext->getType(), VecTy, i);
                 // Add back the cost of s|zext which is subtracted separately.
                 DeadCost += TTI->getCastInstrCost(
-                    Ext->getOpcode(), Ext->getType(), E->getType(), Ext);
+                    Ext->getOpcode(), Ext->getType(),
+                    E->getType(), Ext);
                 continue;
               }
             }
             DeadCost -=
                 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i);
           }
         }
         return DeadCost;
       }
-      return ReuseShuffleCost + getGatherCost(VL);
+      return ReuseShuffleCost + getGatherCost(IL);
 
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::SIToFP:
     case Instruction::UIToFP:
     case Instruction::Trunc:
     case Instruction::FPTrunc:
     case Instruction::BitCast: {
       Type *SrcTy = VL0->getOperand(0)->getType();
       int ScalarEltCost =
-          TTI->getCastInstrCost(S.getOpcode(), ScalarTy, SrcTy, VL0);
+          TTI->getCastInstrCost(IL[0]->MainOpcode, ScalarTy, SrcTy, VL0);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
 
       // Calculate the cost of this instruction.
-      int ScalarCost = VL.size() * ScalarEltCost;
+      int ScalarCost = IL.size() * ScalarEltCost;
 
-      VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size());
+      VectorType *SrcVecTy = VectorType::get(SrcTy, IL.size());
       int VecCost = 0;
       // Check if the values are candidates to demote.
       if (!MinBWs.count(VL0) || VecTy != SrcVecTy) {
         VecCost = ReuseShuffleCost +
-                  TTI->getCastInstrCost(S.getOpcode(), VecTy, SrcVecTy, VL0);
+                  TTI->getCastInstrCost(IL[0]->MainOpcode, VecTy,
+                                        SrcVecTy, VL0);
       }
       return VecCost - ScalarCost;
     }
     case Instruction::FCmp:
     case Instruction::ICmp:
     case Instruction::Select: {
       // Calculate the cost of this instruction.
-      int ScalarEltCost = TTI->getCmpSelInstrCost(S.getOpcode(), ScalarTy,
-                                                  Builder.getInt1Ty(), VL0);
+      int ScalarEltCost = TTI->getCmpSelInstrCost(IL[0]->MainOpcode,
+                                                  ScalarTy,
+                                                  Builder.getInt1Ty(),
+                                                  VL0);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
-      VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size());
+      VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), IL.size());
       int ScalarCost = VecTy->getNumElements() * ScalarEltCost;
-      int VecCost = TTI->getCmpSelInstrCost(S.getOpcode(), VecTy, MaskTy, VL0);
+      int VecCost = TTI->getCmpSelInstrCost(IL[0]->MainOpcode, VecTy,
+                                            MaskTy, VL0);
       return ReuseShuffleCost + VecCost - ScalarCost;
     }
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
case Instruction::Xor: {
       TargetTransformInfo::OperandValueProperties Op2VP =
           TargetTransformInfo::OP_PowerOf2;
 
       // If all operands are exactly the same ConstantInt then set the
       // operand kind to OK_UniformConstantValue.
       // If instead not all operands are constants, then set the operand kind
       // to OK_AnyValue. If all operands are constants but not the same,
       // then set the operand kind to OK_NonUniformConstantValue.
-      ConstantInt *CInt0 = nullptr;
-      for (unsigned i = 0, e = VL.size(); i < e; ++i) {
-        const Instruction *I = cast<Instruction>(VL[i]);
+      ConstantInt *CInt0 = dyn_cast<ConstantInt>(
+                                IL[0]->getOpInst()->getOperand(1));
+      for (auto *IOP : IL) {
+        auto *I = IOP->getOpInst();
         ConstantInt *CInt = dyn_cast<ConstantInt>(I->getOperand(1));
         if (!CInt) {
           Op2VK = TargetTransformInfo::OK_AnyValue;
           Op2VP = TargetTransformInfo::OP_None;
           break;
         }
         if (Op2VP == TargetTransformInfo::OP_PowerOf2 &&
             !CInt->getValue().isPowerOf2())
           Op2VP = TargetTransformInfo::OP_None;
-        if (i == 0) {
-          CInt0 = CInt;
-          continue;
-        }
         if (CInt0 != CInt)
           Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
       }
 
       SmallVector<const Value *, 4> Operands(VL0->operand_values());
       int ScalarEltCost = TTI->getArithmeticInstrCost(
-          S.getOpcode(), ScalarTy, Op1VK, Op2VK, Op1VP, Op2VP, Operands);
+          IL[0]->MainOpcode, ScalarTy, Op1VK, Op2VK, Op1VP, Op2VP, Operands);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
       int ScalarCost = VecTy->getNumElements() * ScalarEltCost;
-      int VecCost = TTI->getArithmeticInstrCost(S.getOpcode(), VecTy, Op1VK,
-                                                Op2VK, Op1VP, Op2VP, Operands);
+      int VecCost = TTI->getArithmeticInstrCost(IL[0]->MainOpcode, VecTy,
+                                                Op1VK, Op2VK, Op1VP, Op2VP,
+                                                Operands);
       return ReuseShuffleCost + VecCost - ScalarCost;
     }
     case Instruction::GetElementPtr: {
       TargetTransformInfo::OperandValueKind Op1VK =
           TargetTransformInfo::OK_AnyValue;
       TargetTransformInfo::OperandValueKind Op2VK =
           TargetTransformInfo::OK_UniformConstantValue;
 
       int ScalarEltCost =
           TTI->getArithmeticInstrCost(Instruction::Add, ScalarTy, Op1VK, Op2VK);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
       int ScalarCost = VecTy->getNumElements() * ScalarEltCost;
       int VecCost =
           TTI->getArithmeticInstrCost(Instruction::Add, VecTy, Op1VK, Op2VK);
       return ReuseShuffleCost + VecCost - ScalarCost;
     }
     case Instruction::Load: {
       // Cost of wide load - cost of scalar loads.
       unsigned alignment = cast<LoadInst>(VL0)->getAlignment();
       int ScalarEltCost =
           TTI->getMemoryOpCost(Instruction::Load, ScalarTy, alignment, 0, VL0);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
       int ScalarLdCost = VecTy->getNumElements() * ScalarEltCost;
       int VecLdCost =
           TTI->getMemoryOpCost(Instruction::Load, VecTy, alignment, 0, VL0);
       if (!E->ReorderIndices.empty()) {
         // TODO: Merge this shuffle with the ReuseShuffleCost.
         VecLdCost += TTI->getShuffleCost(
             TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
       }
       return ReuseShuffleCost + VecLdCost - ScalarLdCost;
     }
     case Instruction::Store: {
       // We know that we can merge the stores. Calculate the cost.
       unsigned alignment = cast<StoreInst>(VL0)->getAlignment();
       int ScalarEltCost =
           TTI->getMemoryOpCost(Instruction::Store, ScalarTy, alignment, 0, VL0);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
       int ScalarStCost = VecTy->getNumElements() * ScalarEltCost;
       int VecStCost =
           TTI->getMemoryOpCost(Instruction::Store, VecTy, alignment, 0, VL0);
       return ReuseShuffleCost + VecStCost - ScalarStCost;
     }
     case Instruction::Call: {
       CallInst *CI = cast<CallInst>(VL0);
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
 
       // Calculate the cost of the scalar and vector calls.
       SmallVector<Type *, 4> ScalarTys;
       for (unsigned op = 0, opc = CI->getNumArgOperands(); op != opc; ++op)
         ScalarTys.push_back(CI->getArgOperand(op)->getType());
 
       FastMathFlags FMF;
       if (auto *FPMO = dyn_cast<FPMathOperator>(CI))
         FMF = FPMO->getFastMathFlags();
 
       int ScalarEltCost =
           TTI->getIntrinsicInstrCost(ID, ScalarTy, ScalarTys, FMF);
       if (NeedToShuffleReuses) {
-        ReuseShuffleCost -= (ReuseShuffleNumbers - VL.size()) * ScalarEltCost;
+        ReuseShuffleCost -= (ReuseShuffleNumbers - IL.size()) * ScalarEltCost;
       }
       int ScalarCallCost = VecTy->getNumElements() * ScalarEltCost;
 
       SmallVector<Value *, 4> Args(CI->arg_operands());
       int VecCallCost = TTI->getIntrinsicInstrCost(ID, CI->getType(), Args, FMF,
                                                    VecTy->getNumElements());
 
       LLVM_DEBUG(dbgs() << "SLP: Call cost " << VecCallCost - ScalarCallCost
                         << " (" << VecCallCost << "-" << ScalarCallCost << ")"
                         << " for " << *CI << "\n");
 
       return ReuseShuffleCost + VecCallCost - ScalarCallCost;
     }
     case Instruction::ShuffleVector: {
-      assert(S.isAltShuffle() &&
-             ((Instruction::isBinaryOp(S.getOpcode()) &&
-               Instruction::isBinaryOp(S.getAltOpcode())) ||
-              (Instruction::isCast(S.getOpcode()) &&
-               Instruction::isCast(S.getAltOpcode()))) &&
+      assert(IL[0]->isAltShuffle() &&
+             ((Instruction::isBinaryOp(IL[0]->MainOpcode) &&
+             Instruction::isBinaryOp(IL[0]->AltOpcode)) ||
+             (Instruction::isCast(IL[0]->MainOpcode) &&
+             Instruction::isCast(IL[0]->AltOpcode))) &&
              "Invalid Shuffle Vector Operand");
       int ScalarCost = 0;
       if (NeedToShuffleReuses) {
         for (unsigned Idx : E->ReuseShuffleIndices) {
-          Instruction *I = cast<Instruction>(VL[Idx]);
           ReuseShuffleCost -= TTI->getInstructionCost(
-              I, TargetTransformInfo::TCK_RecipThroughput);
+              IL[Idx]->getOpInst(), TargetTransformInfo::TCK_RecipThroughput);
         }
-        for (Value *V : VL) {
-          Instruction *I = cast<Instruction>(V);
+        for (auto *IOP : IL) {
           ReuseShuffleCost += TTI->getInstructionCost(
-              I, TargetTransformInfo::TCK_RecipThroughput);
+              IOP->getOpInst(), TargetTransformInfo::TCK_RecipThroughput);
         }
       }
-      for (Value *i : VL) {
-        Instruction *I = cast<Instruction>(i);
-        assert(S.isOpcodeOrAlt(I) && "Unexpected main/alternate opcode");
+      for (auto *IOP : IL) {
+        assert(IOP->isOpcodeOrAlt() && "Unexpected main/alternate opcode");
         ScalarCost += TTI->getInstructionCost(
-            I, TargetTransformInfo::TCK_RecipThroughput);
+            IOP->getOpInst(), TargetTransformInfo::TCK_RecipThroughput);
       }
       // VecCost is equal to sum of the cost of creating 2 vectors
       // and the cost of creating shuffle.
       int VecCost = 0;
-      if (Instruction::isBinaryOp(S.getOpcode())) {
-        VecCost = TTI->getArithmeticInstrCost(S.getOpcode(), VecTy);
-        VecCost += TTI->getArithmeticInstrCost(S.getAltOpcode(), VecTy);
+      if (Instruction::isBinaryOp(IL[0]->MainOpcode)) {
+        VecCost = TTI->getArithmeticInstrCost(IL[0]->MainOpcode, VecTy);
+        VecCost += TTI->getArithmeticInstrCost(IL[0]->AltOpcode, VecTy);
       } else {
-        Type *Src0SclTy = S.MainOp->getOperand(0)->getType();
-        Type *Src1SclTy = S.AltOp->getOperand(0)->getType();
-        VectorType *Src0Ty = VectorType::get(Src0SclTy, VL.size());
-        VectorType *Src1Ty = VectorType::get(Src1SclTy, VL.size());
-        VecCost = TTI->getCastInstrCost(S.getOpcode(), VecTy, Src0Ty);
-        VecCost += TTI->getCastInstrCost(S.getAltOpcode(), VecTy, Src1Ty);
+        Type *Src0SclTy = IL[0]->MainOp->getOperand(0)->getType();
+        Type *Src1SclTy = IL[0]->AltOp->getOperand(0)->getType();
+        VectorType *Src0Ty = VectorType::get(Src0SclTy, IL.size());
+        VectorType *Src1Ty = VectorType::get(Src1SclTy, IL.size());
+        VecCost = TTI->getCastInstrCost(IL[0]->MainOpcode, VecTy, Src0Ty);
+        VecCost += TTI->getCastInstrCost(IL[0]->AltOpcode, VecTy,
+                                         Src1Ty);
       }
       VecCost += TTI->getShuffleCost(TargetTransformInfo::SK_Select, VecTy, 0);
       return ReuseShuffleCost + VecCost - ScalarCost;
     }
     default:
       llvm_unreachable("Unknown instruction");
   }
 }
bool BoUpSLP::isFullyVectorizableTinyTree() {
 
   // Gathering cost would be too much for tiny trees.
   if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather)
     return false;
 
   return true;
 }
 
+Instruction *BoUpSLP::propagateMetadata(Instruction *I,
+                                        ArrayRef<InstructionOrPseudo *> IL) {
+  ValueList VL;
+  for (auto *IOP: IL)
+    VL.push_back(IOP->getOp());
+  return llvm::propagateMetadata(I, VL);
+}
+
+void BoUpSLP::propagateIRFlags(Value *I,
+                               ArrayRef<InstructionOrPseudo *> IL,
+                               Value *OpValue) {
+  ValueList VL;
+  for (auto *IOP: IL)
+    VL.push_back(IOP->getOp());
+  llvm::propagateIRFlags(I, VL, OpValue);
+}
+
 bool BoUpSLP::isTreeTinyAndNotFullyVectorizable() {
   // We can vectorize the tree if its size is greater than or equal to the
   // minimum size specified by the MinTreeSize command line option.
   if (VectorizableTree.size() >= MinTreeSize)
     return false;
 
   // If we have a tiny tree (a tree whose size is less than MinTreeSize), we
   // can vectorize it if we can prove it fully vectorizable.
int BoUpSLP::getSpillCost() {
   // (for example, if spills and fills are required).
   unsigned BundleWidth = VectorizableTree.front().Scalars.size();
   int Cost = 0;
 
   SmallPtrSet<Instruction*, 4> LiveValues;
   Instruction *PrevInst = nullptr;
 
   for (const auto &N : VectorizableTree) {
-    Instruction *Inst = dyn_cast<Instruction>(N.Scalars[0]);
+    Instruction *Inst = N.Scalars[0]->getOpInst();
     if (!Inst)
       continue;
 
     if (!PrevInst) {
       PrevInst = Inst;
       continue;
     }
 
     // Update LiveValues.
     LiveValues.erase(PrevInst);
     for (auto &J : PrevInst->operands()) {
-      if (isa<Instruction>(&*J) && getTreeEntry(&*J))
-        LiveValues.insert(cast<Instruction>(&*J));
+      auto *I = dyn_cast<Instruction>(&*J);
+      if (I && getTreeEntry(I))
+        LiveValues.insert(I);
     }
 
     LLVM_DEBUG({
       dbgs() << "SLP: #LV: " << LiveValues.size();
       for (auto *X : LiveValues)
         dbgs() << " " << X->getName();
       dbgs() << ", Looking at ";
       Inst->dump();
if (TE.NeedToGather &&
         std::any_of(std::next(VectorizableTree.begin(), I + 1),
                     VectorizableTree.end(), [TE](TreeEntry &Entry) {
                       return Entry.NeedToGather && Entry.isSame(TE.Scalars);
                     }))
       continue;
 
     int C = getEntryCost(&TE);
     LLVM_DEBUG(dbgs() << "SLP: Adding cost " << C
-                      << " for bundle that starts with " << *TE.Scalars[0]
-                      << ".\n");
+                      << " for bundle that starts with "
+                      << *TE.Scalars[0]->getOp() << ".\n");
     Cost += C;
   }
 
   SmallPtrSet<Value *, 16> ExtractCostCalculated;
   int ExtractCost = 0;
   for (ExternalUser &EU : ExternalUses) {
     // We only add extract cost once for the same scalar.
     if (!ExtractCostCalculated.insert(EU.Scalar).second)
       continue;
 
     // Uses by ephemeral values are free (because the ephemeral value will be
     // removed prior to code generation, and so the extraction will be
     // removed as well).
     if (EphValues.count(EU.User))
       continue;
 
     // If we plan to rewrite the tree in a smaller type, we will need to sign
     // extend the extracted value back to the original type. Here, we account
     // for the extract and the added cost of the sign extend if needed.
     auto *VecTy = VectorType::get(EU.Scalar->getType(), BundleWidth);
-    auto *ScalarRoot = VectorizableTree[0].Scalars[0];
+    auto *ScalarRoot = VectorizableTree[0].Scalars[0]->getOp();
     if (MinBWs.count(ScalarRoot)) {
       auto *MinTy = IntegerType::get(F->getContext(), MinBWs[ScalarRoot].first);
       auto Extend =
           MinBWs[ScalarRoot].second ? Instruction::SExt : Instruction::ZExt;
       VecTy = VectorType::get(MinTy, BundleWidth);
       ExtractCost += TTI->getExtractWithExtendCost(Extend, EU.Scalar->getType(),
                                                    VecTy, EU.Lane);
     } else {
int BoUpSLP::getGatherCost(Type *Ty,
   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
     if (!ShuffledIndices.count(i))
       Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
   if (!ShuffledIndices.empty())
       Cost += TTI->getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, Ty);
   return Cost;
 }
 
-int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
-  // Find the type of the operands in VL.
-  Type *ScalarTy = VL[0]->getType();
-  if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
+int BoUpSLP::getGatherCost(ArrayRef<InstructionOrPseudo *> IL) {
+  // Find the type of the operands in IL.
+  Value *V = IL[0]->getOp();
+  Type *ScalarTy = V->getType();
+  if (StoreInst *SI = dyn_cast<StoreInst>(V))
     ScalarTy = SI->getValueOperand()->getType();
-  VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
+  VectorType *VecTy = VectorType::get(ScalarTy, IL.size());
   // Find the cost of inserting/extracting values from the vector.
   // Check if the same elements are inserted several times and count them as
   // shuffle candidates.
   DenseSet<unsigned> ShuffledElements;
   DenseSet<Value *> UniqueElements;
   // Iterate in reverse order to consider insert elements with the high cost.
-  for (unsigned I = VL.size(); I > 0; --I) {
+  for (unsigned I = IL.size(); I > 0; --I) {
     unsigned Idx = I - 1;
-    if (!UniqueElements.insert(VL[Idx]).second)
+    if (!UniqueElements.insert(IL[Idx]->getOp()).second)
       ShuffledElements.insert(Idx);
   }
   return getGatherCost(VecTy, ShuffledElements);
 }
 
 // Reorder commutative operations in alternate shuffle if the resulting vectors
 // are consecutive loads. This would allow us to vectorize the tree.
 // 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.
-void BoUpSLP::reorderAltShuffleOperands(const InstructionsState &S,
-                                        ArrayRef<Value *> VL,
+void BoUpSLP::reorderAltShuffleOperands(ArrayRef<InstructionOrPseudo *> IL,
                                         SmallVectorImpl<Value *> &Left,
                                         SmallVectorImpl<Value *> &Right) {
   // 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");
+  for (auto *Inst : IL) {
+    auto *I = Inst->getOpInst();
+    assert(Inst->isOpcodeOrAlt() && "Incorrect instruction in vector");
     Left.push_back(I->getOperand(0));
     Right.push_back(I->getOperand(1));
   }
 
   // Reorder if we have a commutative operation and consecutive access
   // are on either side of the alternate instructions.
-  for (unsigned j = 0; j < VL.size() - 1; ++j) {
+  for (unsigned j = 0; j < IL.size() - 1; ++j) {
     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
-        Instruction *VL1 = cast<Instruction>(VL[j]);
-        Instruction *VL2 = cast<Instruction>(VL[j + 1]);
+        Instruction *VL1 = IL[j]->getOpInst();
+        Instruction *VL2 = IL[j + 1]->getOpInst();
         if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) {
           std::swap(Left[j], Right[j]);
           continue;
         } else if (VL2->isCommutative() &&
                    isConsecutiveAccess(L, L1, *DL, *SE)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
         // else unchanged
       }
     }
     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
-        Instruction *VL1 = cast<Instruction>(VL[j]);
-        Instruction *VL2 = cast<Instruction>(VL[j + 1]);
+        Instruction *VL1 = IL[j]->getOpInst();
+        Instruction *VL2 = IL[j + 1]->getOpInst();
         if (VL1->isCommutative() && isConsecutiveAccess(L, L1, *DL, *SE)) {
           std::swap(Left[j], Right[j]);
           continue;
         } else if (VL2->isCommutative() &&
                    isConsecutiveAccess(L, L1, *DL, *SE)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
if (AllSameOpcodeLeft) {
     if (ILeft && LeftPrevOpcode == ILeft->getOpcode())
       return false;
     if (IRight && LeftPrevOpcode == IRight->getOpcode())
       return true;
   }
   return false;
 }
 
-void BoUpSLP::reorderInputsAccordingToOpcode(unsigned Opcode,
-                                             ArrayRef<Value *> VL,
+void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<InstructionOrPseudo *> IL,
                                              SmallVectorImpl<Value *> &Left,
                                              SmallVectorImpl<Value *> &Right) {
-  if (!VL.empty()) {
+  if (!IL.empty()) {
     // Peel the first iteration out of the loop since there's nothing
     // interesting to do anyway and it simplifies the checks in the loop.
-    auto *I = cast<Instruction>(VL[0]);
+    auto *I = IL[0]->getOpInst();
     Value *VLeft = I->getOperand(0);
     Value *VRight = I->getOperand(1);
     if (!isa<Instruction>(VRight) && isa<Instruction>(VLeft))
       // Favor having instruction to the right. FIXME: why?
       std::swap(VLeft, VRight);
     Left.push_back(VLeft);
     Right.push_back(VRight);
   }
+  unsigned Opcode = IL[0]->MainOpcode;
 
   // 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]);
+  for (unsigned i = 1, e = IL.size(); i != e; ++i) {
+    Instruction *I = IL[i]->getOpInst();
     assert(((I->getOpcode() == Opcode && I->isCommutative()) ||
             (I->getOpcode() != Opcode && Instruction::isCommutative(Opcode))) &&
            "Can only process commutative instruction");
     // Commute to favor either a splat or maximizing having the same opcodes on
     // one side.
     Value *VLeft;
     Value *VRight;
     if (shouldReorderOperands(i, Opcode, *I, Left, Right, AllSameOpcodeLeft,
void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<InstructionOrPseudo *> IL,
   // 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) {
+  for (unsigned j = 0, e = IL.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)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
       }
     }
     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
         if (isConsecutiveAccess(L, L1, *DL, *SE)) {
           std::swap(Left[j + 1], Right[j + 1]);
           continue;
         }
       }
     }
     // else unchanged
   }
 }
 
-void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL,
-                                        const InstructionsState &S) {
+void BoUpSLP::setInsertPointAfterBundle(ArrayRef<InstructionOrPseudo *> IL) {
   // 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 *Front = IL[0]->MainOp;
   auto *BB = Front->getParent();
-  assert(llvm::all_of(make_range(VL.begin(), VL.end()), [=](Value *V) -> bool {
-    auto *I = cast<Instruction>(V);
-    return !S.isOpcodeOrAlt(I) || I->getParent() == BB;
+  assert(llvm::all_of(
+      make_range(IL.begin(), IL.end()), [=](InstructionOrPseudo *I) -> bool {
+        return !I->isOpcodeOrAlt() || I->getOpInst()->getParent() == BB;
       }));
 
   // The last instruction in the bundle in program order.
   Instruction *LastInst = nullptr;
 
-  // Find the last instruction. The common case should be that BB has been
-  // scheduled, and the last instruction is VL.back(). So we start with
-  // VL.back() and iterate over schedule data until we reach the end of the
-  // bundle. The end of the bundle is marked by null ScheduleData.
+  // Find the last instruction. If the bundle is not scheduled then
+  // the first in the bundle is the last one in BB, because we discover
+  // bundles in backward walk.
   if (BlocksSchedules.count(BB)) {
-    auto *Bundle =
-        BlocksSchedules[BB]->getScheduleData(isOneOf(S, VL.back()));
+    BlockScheduling *BS = BlocksSchedules[BB].get();
+    auto *Bundle = BS->getScheduleData(IL[0]);
     if (Bundle && Bundle->isPartOfBundle())
-      for (; Bundle; Bundle = Bundle->NextInBundle)
-        if (Bundle->OpValue == Bundle->Inst)
-          LastInst = Bundle->Inst;
+      LastInst = Bundle->FirstInBundle->Inst;
   }
 
   // LastInst can still be null at this point if there's either not an entry
   // for BB in BlocksSchedules or there's no ScheduleData available for
   // VL.back(). This can be the case if buildTree_rec aborts for various
   // reasons (e.g., the maximum recursion depth is reached, the maximum region
   // size is reached, etc.). ScheduleData is initialized in the scheduling
   // "dry-run".
   //
   // If this happens, we can still find the last instruction by brute force. We
   // iterate forwards from Front (inclusive) until we either see all
   // instructions in the bundle or reach the end of the block. If Front is the
   // last instruction in program order, LastInst will be set to Front, and we
   // will visit all the remaining instructions in the block.
   //
   // One of the reasons we exit early from buildTree_rec is to place an upper
   // bound on compile-time. Thus, taking an additional compile-time hit here is
   // not ideal. However, this should be exceedingly rare since it requires that
   // we both exit early from buildTree_rec and that the bundle be out-of-order
   // (causing us to iterate all the way to the end of the block).
   if (!LastInst) {
-    SmallPtrSet<Value *, 16> Bundle(VL.begin(), VL.end());
+    SmallPtrSet<Value *, 16> Bundle;
+    for (auto *IOP : IL)
+      Bundle.insert(IOP->getOp());
     for (auto &I : make_range(BasicBlock::iterator(Front), BB->end())) {
-      if (Bundle.erase(&I) && S.isOpcodeOrAlt(&I))
+      if (Bundle.erase(&I))
         LastInst = &I;
       if (Bundle.empty())
         break;
     }
   }
 
   // Set the insertion point after the last instruction in the bundle. Set the
   // debug location to Front.
   Builder.SetInsertPoint(BB, ++LastInst->getIterator());
   Builder.SetCurrentDebugLocation(Front->getDebugLoc());
 }
 
-Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
+Value *BoUpSLP::Gather(ArrayRef<InstructionOrPseudo *> IL, VectorType *Ty) {
   Value *Vec = UndefValue::get(Ty);
   // Generate the 'InsertElement' instruction.
   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
-    Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
+    auto *Op = IL[i]->getOp();
+    Vec = Builder.CreateInsertElement(Vec, Op, Builder.getInt32(i));
     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
       GatherSeq.insert(Insrt);
       CSEBlocks.insert(Insrt->getParent());
 
       // Add to our 'need-to-extract' list.
-      if (TreeEntry *E = getTreeEntry(VL[i])) {
+      if (TreeEntry *E = getTreeEntry(Op)) {
         // Find which lane we need to extract.
         int FoundLane = -1;
         for (unsigned Lane = 0, LE = E->Scalars.size(); Lane != LE; ++Lane) {
           // Is this the lane of the scalar that we are looking for ?
-          if (E->Scalars[Lane] == VL[i]) {
+          if (E->Scalars[Lane]->isEqual(IL[i])) {
             FoundLane = Lane;
             break;
           }
         }
         assert(FoundLane >= 0 && "Could not find the correct lane");
         if (!E->ReuseShuffleIndices.empty()) {
           FoundLane =
               std::distance(E->ReuseShuffleIndices.begin(),
                             llvm::find(E->ReuseShuffleIndices, FoundLane));
         }
-        ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
+        ExternalUses.push_back(ExternalUser(Op, Insrt, FoundLane));
       }
     }
   }
 
   return Vec;
 }
 
-Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
-  InstructionsState S = getSameOpcode(VL);
-  if (S.getOpcode()) {
-    if (TreeEntry *E = getTreeEntry(S.OpValue)) {
-      if (E->isSame(VL)) {
-        Value *V = vectorizeTree(E);
-        if (VL.size() == E->Scalars.size() && !E->ReuseShuffleIndices.empty()) {
-          // We need to get the vectorized value but without shuffle.
-          if (auto *SV = dyn_cast<ShuffleVectorInst>(V)) {
-            V = SV->getOperand(0);
-          } else {
-            // Reshuffle to get only unique values.
-            SmallVector<unsigned, 4> UniqueIdxs;
-            SmallSet<unsigned, 4> UsedIdxs;
-            for(unsigned Idx : E->ReuseShuffleIndices)
-              if (UsedIdxs.insert(Idx).second)
+Value *BoUpSLP::vectorizeTree(Value *Parent, ArrayRef<Value *> VL) {
+  IOPList IL;
+  for (Value *V: VL)
+    IL.push_back(allocInstructionOrPseudo(Parent, V));
+  InstructionsState S = getSameOpcode(IL);
+  for (InstructionOrPseudo *IOP: IL)
+    IOP->setInstructionsState(S);
+  if (IL[0]->MainOp) {
+    TreeEntry *E = getTreeEntry(IL[0]->MainOp);
+    if (E && E->isSame(IL)) {
+          for (unsigned Idx : E->ReuseShuffleIndices)
                 UniqueIdxs.emplace_back(Idx);
-            V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
-                                            UniqueIdxs);
-          }
-        }
-        return V;
-      }
-    }
-  }
 
   Type *ScalarTy = S.OpValue->getType();
   if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
     ScalarTy = SI->getValueOperand()->getType();
 
   // Check that every instruction appears once in this bundle.
   SmallVector<unsigned, 4> ReuseShuffleIndicies;
-  SmallVector<Value *, 4> UniqueValues;
-  if (VL.size() > 2) {
+  IOPList UniqueValues;
+  if (IL.size() > 2) {
     DenseMap<Value *, unsigned> UniquePositions;
-    for (Value *V : VL) {
+    for (auto *I : IL) {
+      Value *V = I->getOp();
       auto Res = UniquePositions.try_emplace(V, UniqueValues.size());
       ReuseShuffleIndicies.emplace_back(Res.first->second);
       if (Res.second || isa<Constant>(V))
-        UniqueValues.emplace_back(V);
+        UniqueValues.emplace_back(I);
     }
     // Do not shuffle single element or if number of unique values is not power
     // of 2.
-    if (UniqueValues.size() == VL.size() || UniqueValues.size() <= 1 ||
+    if (UniqueValues.size() == IL.size() || UniqueValues.size() <= 1 ||
         !llvm::isPowerOf2_32(UniqueValues.size()))
       ReuseShuffleIndicies.clear();
     else
-      VL = UniqueValues;
+      IL = UniqueValues;
   }
-  VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
+  VectorType *VecTy = VectorType::get(ScalarTy, IL.size());
 
-  Value *V = Gather(VL, VecTy);
+  Value *V = Gather(IL, VecTy);
   if (!ReuseShuffleIndicies.empty()) {
     V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                     ReuseShuffleIndicies, "shuffle");
     if (auto *I = dyn_cast<Instruction>(V)) {
       GatherSeq.insert(I);
       CSEBlocks.insert(I->getParent());
     }
   }
   return V;
 }
 
 static void inversePermutation(ArrayRef<unsigned> Indices,
                                SmallVectorImpl<unsigned> &Mask) {
   Mask.clear();
   const unsigned E = Indices.size();
   Mask.resize(E);
   for (unsigned I = 0; I < E; ++I)
     Mask[Indices[I]] = I;
 }
 
 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
   IRBuilder<>::InsertPointGuard Guard(Builder);
 
   if (E->VectorizedValue) {
-    LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
+    LLVM_DEBUG(dbgs() << "SLP: Diamond merged for "
+                      << *E->Scalars[0]->MainOp << ".\n");
     return E->VectorizedValue;
   }
 
-  InstructionsState S = getSameOpcode(E->Scalars);
-  Instruction *VL0 = cast<Instruction>(S.OpValue);
+  auto *VL0 = E->Scalars[0]->MainOp;
   Type *ScalarTy = VL0->getType();
   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
     ScalarTy = SI->getValueOperand()->getType();
   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
 
   bool NeedToShuffleReuses = !E->ReuseShuffleIndices.empty();
 
   if (E->NeedToGather) {
-    setInsertPointAfterBundle(E->Scalars, S);
+    setInsertPointAfterBundle(E->Scalars);
     auto *V = Gather(E->Scalars, VecTy);
     if (NeedToShuffleReuses) {
       V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                       E->ReuseShuffleIndices, "shuffle");
       if (auto *I = dyn_cast<Instruction>(V)) {
         GatherSeq.insert(I);
         CSEBlocks.insert(I->getParent());
       }
     }
     E->VectorizedValue = V;
     return V;
   }
 
-  unsigned ShuffleOrOp = S.isAltShuffle() ?
-           (unsigned) Instruction::ShuffleVector : S.getOpcode();
+  unsigned ShuffleOrOp = E->Scalars[0]->isAltShuffle() ?
+           (unsigned) Instruction::ShuffleVector : E->Scalars[0]->MainOpcode;
   switch (ShuffleOrOp) {
     case Instruction::PHI: {
       PHINode *PH = dyn_cast<PHINode>(VL0);
       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
       Value *V = NewPhi;
       if (NeedToShuffleReuses) {
case Instruction::PHI: {
         BasicBlock *IBB = PH->getIncomingBlock(i);
 
         if (!VisitedBBs.insert(IBB).second) {
           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
           continue;
         }
 
         // Prepare the operand vector.
-        for (Value *V : E->Scalars)
-          Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(IBB));
+        for (auto *IOP : E->Scalars)
+          Operands.push_back(
+              cast<PHINode>(IOP->getOp())->getIncomingValueForBlock(IBB));
 
         Builder.SetInsertPoint(IBB->getTerminator());
         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
-        Value *Vec = vectorizeTree(Operands);
+        Value *Vec = vectorizeTree(VL0, Operands);
         NewPhi->addIncoming(Vec, IBB);
       }
 
       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
              "Invalid number of incoming values");
       return V;
     }
 
case Instruction::ExtractElement: {
           if (E->ReorderIndices.empty())
             Builder.SetInsertPoint(VL0);
           V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                           E->ReuseShuffleIndices, "shuffle");
         }
         E->VectorizedValue = V;
         return V;
       }
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
       auto *V = Gather(E->Scalars, VecTy);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
         if (auto *I = dyn_cast<Instruction>(V)) {
           GatherSeq.insert(I);
           CSEBlocks.insert(I->getParent());
         }
case Instruction::ExtractValue: {
         if (NeedToShuffleReuses) {
           // TODO: Merge this shuffle with the ReorderShuffleMask.
           NewV = Builder.CreateShuffleVector(
               NewV, UndefValue::get(VecTy), E->ReuseShuffleIndices, "shuffle");
         }
         E->VectorizedValue = NewV;
         return NewV;
       }
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
       auto *V = Gather(E->Scalars, VecTy);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
         if (auto *I = dyn_cast<Instruction>(V)) {
           GatherSeq.insert(I);
           CSEBlocks.insert(I->getParent());
         }
switch (ShuffleOrOp) {
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::SIToFP:
     case Instruction::UIToFP:
     case Instruction::Trunc:
     case Instruction::FPTrunc:
     case Instruction::BitCast: {
       ValueList INVL;
-      for (Value *V : E->Scalars)
-        INVL.push_back(cast<Instruction>(V)->getOperand(0));
+      for (auto *IOP : E->Scalars)
+        INVL.push_back(IOP->getOpInst()->getOperand(0));
 
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
-      Value *InVec = vectorizeTree(INVL);
+      Value *InVec = vectorizeTree(VL0, INVL);
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       CastInst *CI = dyn_cast<CastInst>(VL0);
       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::FCmp:
     case Instruction::ICmp: {
       ValueList LHSV, RHSV;
-      for (Value *V : E->Scalars) {
-        LHSV.push_back(cast<Instruction>(V)->getOperand(0));
-        RHSV.push_back(cast<Instruction>(V)->getOperand(1));
+      for (auto *IOP : E->Scalars) {
+        auto *I = IOP->getOpInst();
+        LHSV.push_back(I->getOperand(0));
+        RHSV.push_back(I->getOperand(1));
       }
 
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
-      Value *L = vectorizeTree(LHSV);
-      Value *R = vectorizeTree(RHSV);
+      Value *L = vectorizeTree(VL0, LHSV);
+      Value *R = vectorizeTree(VL0, RHSV);
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
       Value *V;
-      if (S.getOpcode() == Instruction::FCmp)
+      if (E->Scalars[0]->MainOpcode == Instruction::FCmp)
         V = Builder.CreateFCmp(P0, L, R);
       else
         V = Builder.CreateICmp(P0, L, R);
 
       propagateIRFlags(V, E->Scalars, VL0);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::Select: {
       ValueList TrueVec, FalseVec, CondVec;
-      for (Value *V : E->Scalars) {
-        CondVec.push_back(cast<Instruction>(V)->getOperand(0));
-        TrueVec.push_back(cast<Instruction>(V)->getOperand(1));
-        FalseVec.push_back(cast<Instruction>(V)->getOperand(2));
+      for (auto *IOP : E->Scalars) {
+        auto *I = IOP->getOpInst();
+        CondVec.push_back(I->getOperand(0));
+        TrueVec.push_back(I->getOperand(1));
+        FalseVec.push_back(I->getOperand(2));
       }
 
-      setInsertPointAfterBundle(E->Scalars, S);
-
-      Value *Cond = vectorizeTree(CondVec);
-      Value *True = vectorizeTree(TrueVec);
-      Value *False = vectorizeTree(FalseVec);
+      setInsertPointAfterBundle(E->Scalars);
+
+      Value *Cond = vectorizeTree(VL0, CondVec);
+      Value *True = vectorizeTree(VL0, TrueVec);
+      Value *False = vectorizeTree(VL0, FalseVec);
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       Value *V = Builder.CreateSelect(Cond, True, False);
       if (NeedToShuffleReuses) {
switch (ShuffleOrOp) {
     case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor: {
       ValueList LHSVL, RHSVL;
-      if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
-        reorderInputsAccordingToOpcode(S.getOpcode(), E->Scalars, LHSVL,
-                                       RHSVL);
-      else
-        for (Value *V : E->Scalars) {
-          auto *I = cast<Instruction>(V);
-          LHSVL.push_back(I->getOperand(0));
-          RHSVL.push_back(I->getOperand(1));
-        }
+      if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
+        reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
+      } else
+      for (auto *IOP : E->Scalars) {
+        auto *I = IOP->getOpInst();
 
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
-      Value *LHS = vectorizeTree(LHSVL);
-      Value *RHS = vectorizeTree(RHSVL);
+      Value *LHS = vectorizeTree(VL0, LHSVL);
+      Value *RHS = vectorizeTree(VL0, RHSVL);
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       Value *V = Builder.CreateBinOp(
-          static_cast<Instruction::BinaryOps>(S.getOpcode()), LHS, RHS);
+          static_cast<Instruction::BinaryOps>(VL0->getOpcode()), LHS, RHS);
       propagateIRFlags(V, E->Scalars, VL0);
       if (auto *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
 
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Load: {
       // Loads are inserted at the head of the tree because we don't want to
       // sink them all the way down past store instructions.
       bool IsReorder = !E->ReorderIndices.empty();
       if (IsReorder) {
-        S = getSameOpcode(E->Scalars, E->ReorderIndices.front());
+        InstructionsState S = getSameOpcode(E->Scalars,
+                                            E->ReorderIndices.front());
         VL0 = cast<Instruction>(S.OpValue);
       }
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
       LoadInst *LI = cast<LoadInst>(VL0);
       Type *ScalarLoadTy = LI->getType();
       unsigned AS = LI->getPointerAddressSpace();
 
       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
                                             VecTy->getPointerTo(AS));
 
case Instruction::Load: {
       return V;
     }
     case Instruction::Store: {
       StoreInst *SI = cast<StoreInst>(VL0);
       unsigned Alignment = SI->getAlignment();
       unsigned AS = SI->getPointerAddressSpace();
 
       ValueList ScalarStoreValues;
-      for (Value *V : E->Scalars)
-        ScalarStoreValues.push_back(cast<StoreInst>(V)->getValueOperand());
+      for (auto *IOP : E->Scalars)
+        ScalarStoreValues.push_back(
+            cast<StoreInst>(IOP->getOpInst())->getValueOperand());
 
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
-      Value *VecValue = vectorizeTree(ScalarStoreValues);
+      Value *VecValue = vectorizeTree(VL0, ScalarStoreValues);
       Value *ScalarPtr = SI->getPointerOperand();
       Value *VecPtr = Builder.CreateBitCast(ScalarPtr, VecTy->getPointerTo(AS));
       StoreInst *ST = Builder.CreateStore(VecValue, VecPtr);
 
       // The pointer operand uses an in-tree scalar, so add the new BitCast to
       // ExternalUses to make sure that an extract will be generated in the
       // future.
       if (getTreeEntry(ScalarPtr))
         ExternalUses.push_back(ExternalUser(ScalarPtr, cast<User>(VecPtr), 0));
 
       if (!Alignment)
         Alignment = DL->getABITypeAlignment(SI->getValueOperand()->getType());
 
       ST->setAlignment(Alignment);
       Value *V = propagateMetadata(ST, E->Scalars);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::GetElementPtr: {
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
 
       ValueList Op0VL;
-      for (Value *V : E->Scalars)
-        Op0VL.push_back(cast<GetElementPtrInst>(V)->getOperand(0));
+      for (auto *IOP : E->Scalars) {
+        auto *I = IOP->getOpInst();
+        Op0VL.push_back(cast<GetElementPtrInst>(I)->getOperand(0));
+      }
 
-      Value *Op0 = vectorizeTree(Op0VL);
+      Value *Op0 = vectorizeTree(VL0, Op0VL);
 
       std::vector<Value *> OpVecs;
       for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e;
            ++j) {
         ValueList OpVL;
-        for (Value *V : E->Scalars)
-          OpVL.push_back(cast<GetElementPtrInst>(V)->getOperand(j));
+        for (auto *IOP : E->Scalars) {
+          auto *I = IOP->getOpInst();
+          OpVL.push_back(cast<GetElementPtrInst>(I)->getOperand(j));
+        }
 
-        Value *OpVec = vectorizeTree(OpVL);
+        Value *OpVec = vectorizeTree(VL0, OpVL);
         OpVecs.push_back(OpVec);
       }
 
       Value *V = Builder.CreateGEP(
           cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs);
       if (Instruction *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
 
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
 
       return V;
     }
     case Instruction::Call: {
       CallInst *CI = cast<CallInst>(VL0);
-      setInsertPointAfterBundle(E->Scalars, S);
+      setInsertPointAfterBundle(E->Scalars);
       Function *FI;
       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
       Value *ScalarArg = nullptr;
       if (CI && (FI = CI->getCalledFunction())) {
         IID = FI->getIntrinsicID();
       }
       std::vector<Value *> OpVecs;
       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
         ValueList OpVL;
         // ctlz,cttz and powi are special intrinsics whose second argument is
         // a scalar. This argument should not be vectorized.
         if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) {
           CallInst *CEI = cast<CallInst>(VL0);
           ScalarArg = CEI->getArgOperand(j);
           OpVecs.push_back(CEI->getArgOperand(j));
           continue;
         }
-        for (Value *V : E->Scalars) {
-          CallInst *CEI = cast<CallInst>(V);
+        for (auto *IOP : E->Scalars) {
+          CallInst *CEI = cast<CallInst>(IOP->getOpInst());
           OpVL.push_back(CEI->getArgOperand(j));
         }
 
-        Value *OpVec = vectorizeTree(OpVL);
+        Value *OpVec = vectorizeTree(VL0, OpVL);
         LLVM_DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
         OpVecs.push_back(OpVec);
       }
 
       Module *M = F->getParent();
       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
case Instruction::Call: {
                                         E->ReuseShuffleIndices, "shuffle");
       }
       E->VectorizedValue = V;
       ++NumVectorInstructions;
       return V;
     }
     case Instruction::ShuffleVector: {
       ValueList LHSVL, RHSVL;
-      assert(S.isAltShuffle() &&
-             ((Instruction::isBinaryOp(S.getOpcode()) &&
-               Instruction::isBinaryOp(S.getAltOpcode())) ||
-              (Instruction::isCast(S.getOpcode()) &&
-               Instruction::isCast(S.getAltOpcode()))) &&
+      assert(E->Scalars[0]->isAltShuffle() &&
+             ((Instruction::isBinaryOp(E->Scalars[0]->MainOpcode) &&
+             Instruction::isBinaryOp(E->Scalars[0]->AltOpcode)) ||
+             (Instruction::isCast(E->Scalars[0]->MainOpcode) &&
+             Instruction::isCast(E->Scalars[0]->AltOpcode))) &&
              "Invalid Shuffle Vector Operand");
 
       Value *LHS, *RHS;
-      if (Instruction::isBinaryOp(S.getOpcode())) {
-        reorderAltShuffleOperands(S, E->Scalars, LHSVL, RHSVL);
-        setInsertPointAfterBundle(E->Scalars, S);
-        LHS = vectorizeTree(LHSVL);
-        RHS = vectorizeTree(RHSVL);
+      if (Instruction::isBinaryOp(E->Scalars[0]->MainOpcode)) {
+        reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL);
+        setInsertPointAfterBundle(E->Scalars);
+        LHS = vectorizeTree(VL0, LHSVL);
+        RHS = vectorizeTree(VL0, RHSVL);
       } else {
         ValueList INVL;
-        for (Value *V : E->Scalars)
-          INVL.push_back(cast<Instruction>(V)->getOperand(0));
-        setInsertPointAfterBundle(E->Scalars, S);
-        LHS = vectorizeTree(INVL);
+        for (auto *IOP : E->Scalars)
+          INVL.push_back(IOP->getOpInst()->getOperand(0));
+        setInsertPointAfterBundle(E->Scalars);
+        LHS = vectorizeTree(VL0, INVL);
       }
 
       if (E->VectorizedValue) {
         LLVM_DEBUG(dbgs() << "SLP: Diamond merged for " << *VL0 << ".\n");
         return E->VectorizedValue;
       }
 
       Value *V0, *V1;
-      if (Instruction::isBinaryOp(S.getOpcode())) {
+      if (Instruction::isBinaryOp(E->Scalars[0]->MainOpcode)) {
         V0 = Builder.CreateBinOp(
-          static_cast<Instruction::BinaryOps>(S.getOpcode()), LHS, RHS);
+          static_cast<Instruction::BinaryOps>(E->Scalars[0]->MainOpcode), LHS,
+          RHS);
         V1 = Builder.CreateBinOp(
-          static_cast<Instruction::BinaryOps>(S.getAltOpcode()), LHS, RHS);
+          static_cast<Instruction::BinaryOps>(E->Scalars[0]->AltOpcode), LHS,
+          RHS);
       } else {
         V0 = Builder.CreateCast(
-            static_cast<Instruction::CastOps>(S.getOpcode()), LHS, VecTy);
+            static_cast<Instruction::CastOps>(E->Scalars[0]->MainOpcode), LHS,
+            VecTy);
         V1 = Builder.CreateCast(
-            static_cast<Instruction::CastOps>(S.getAltOpcode()), LHS, VecTy);
+            static_cast<Instruction::CastOps>(E->Scalars[0]->AltOpcode), LHS,
+            VecTy);
       }
 
       // Create shuffle to take alternate operations from the vector.
       // Also, gather up main and alt scalar ops to propagate IR flags to
       // each vector operation.
-      ValueList OpScalars, AltScalars;
+      IOPList OpScalars, AltScalars;
       unsigned e = E->Scalars.size();
       SmallVector<Constant *, 8> Mask(e);
       for (unsigned i = 0; i < e; ++i) {
-        auto *OpInst = cast<Instruction>(E->Scalars[i]);
-        assert(S.isOpcodeOrAlt(OpInst) && "Unexpected main/alternate opcode");
-        if (OpInst->getOpcode() == S.getAltOpcode()) {
+        auto *I = E->Scalars[i]->getOpInst();
+        if (I->getOpcode() == E->Scalars[0]->AltOpcode) {
           Mask[i] = Builder.getInt32(e + i);
           AltScalars.push_back(E->Scalars[i]);
         } else {
           Mask[i] = Builder.getInt32(i);
           OpScalars.push_back(E->Scalars[i]);
         }
       }
 
       Value *ShuffleMask = ConstantVector::get(Mask);
-      propagateIRFlags(V0, OpScalars);
-      propagateIRFlags(V1, AltScalars);
+      InstructionsState S = getSameOpcode(OpScalars);
+      propagateIRFlags(V0, OpScalars, S.OpValue);
+      S = getSameOpcode(AltScalars);
+      propagateIRFlags(V1, AltScalars, S.OpValue);
 
       Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask);
       if (Instruction *I = dyn_cast<Instruction>(V))
         V = propagateMetadata(I, E->Scalars);
       if (NeedToShuffleReuses) {
         V = Builder.CreateShuffleVector(V, UndefValue::get(VecTy),
                                         E->ReuseShuffleIndices, "shuffle");
       }

 
 Value *BoUpSLP::vectorizeTree() {
   ExtraValueToDebugLocsMap ExternallyUsedValues;
   return vectorizeTree(ExternallyUsedValues);
 }
 
 Value *
 BoUpSLP::vectorizeTree(ExtraValueToDebugLocsMap &ExternallyUsedValues) {
-  // All blocks must be scheduled before any instructions are inserted.
   for (auto &BSIter : BlocksSchedules) {
-    scheduleBlock(BSIter.second.get());
+    BlockScheduling *BS = BSIter.second.get();
+    eliminatePseudos(BS);
+    scheduleBlock(BS);
   }
 
   Builder.SetInsertPoint(&F->getEntryBlock().front());
   auto *VectorRoot = vectorizeTree(&VectorizableTree[0]);
 
   // If the vectorized tree can be rewritten in a smaller type, we truncate the
   // vectorized root. InstCombine will then rewrite the entire expression. We
   // sign extend the extracted values below.
-  auto *ScalarRoot = VectorizableTree[0].Scalars[0];
+  auto *ScalarRoot = VectorizableTree[0].Scalars[0]->MainOp;
   if (MinBWs.count(ScalarRoot)) {
     if (auto *I = dyn_cast<Instruction>(VectorRoot))
       Builder.SetInsertPoint(&*++BasicBlock::iterator(I));
     auto BundleWidth = VectorizableTree[0].Scalars.size();
     auto *MinTy = IntegerType::get(F->getContext(), MinBWs[ScalarRoot].first);
     auto *VecTy = VectorType::get(MinTy, BundleWidth);
     auto *Trunc = Builder.CreateTrunc(VectorRoot, VecTy);
     VectorizableTree[0].VectorizedValue = Trunc;
for (TreeEntry &EIdx : VectorizableTree) {
     // No need to handle users of gathered values.
     if (Entry->NeedToGather)
       continue;
 
     assert(Entry->VectorizedValue && "Can't find vectorizable value");
 
     // For each lane:
     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
-      Value *Scalar = Entry->Scalars[Lane];
+      Value *Scalar = Entry->Scalars[Lane]->getOp();
 
       Type *Ty = Scalar->getType();
       if (!Ty->isVoidTy()) {
 #ifndef NDEBUG
         for (User *U : Scalar->users()) {
           LLVM_DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
 
           // It is legal to replace users in the ignorelist by undef.
-          assert((getTreeEntry(U) || is_contained(UserIgnoreList, U)) &&
+          assert((getTreeEntry(U) ||
+                  is_contained(UserIgnoreList, U)) &&
                  "Replacing out-of-tree value with undef");
         }
 #endif
         Value *Undef = UndefValue::get(Ty);
         Scalar->replaceAllUsesWith(Undef);
       }
       LLVM_DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
       eraseInstruction(cast<Instruction>(Scalar));
for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
     }
   }
   CSEBlocks.clear();
   GatherSeq.clear();
 }
 
 // Groups the instructions to a bundle (which is then a single scheduling entity)
 // and schedules instructions until the bundle gets ready.
-bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL,
-                                                 BoUpSLP *SLP,
-                                                 const InstructionsState &S) {
-  if (isa<PHINode>(S.OpValue))
+bool BoUpSLP::BlockScheduling::tryScheduleBundle(
+    ArrayRef<InstructionOrPseudo *> IL, BoUpSLP *SLP) {
+  if (isa<PHINode>(IL[0]->MainOp))
     return true;
 
   // Initialize the instruction bundle.
   Instruction *OldScheduleEnd = ScheduleEnd;
   ScheduleData *PrevInBundle = nullptr;
   ScheduleData *Bundle = nullptr;
   bool ReSchedule = false;
-  LLVM_DEBUG(dbgs() << "SLP:  bundle: " << *S.OpValue << "\n");
+  bool IsPseudo = false;
+  LLVM_DEBUG(dbgs() << "SLP:  bundle: " << *IL[0]->MainOp << "\n");
 
   // Make sure that the scheduling region contains all
   // instructions of the bundle.
-  for (Value *V : VL) {
-    if (!extendSchedulingRegion(V, S))
+  for (InstructionOrPseudo *IOP : IL)
+    if (!extendSchedulingRegion(IOP))
       return false;
-  }
 
-  for (Value *V : VL) {
-    ScheduleData *BundleMember = getScheduleData(V);
+  for (InstructionOrPseudo *IOP : IL) {
+    ScheduleData *BundleMember =
+         ScheduleDataMap[IOP->getOpInst()][std::make_pair(nullptr, 0)];
+    if (BundleMember->isPartOfBundle()) {
+      BundleMember = getScheduleData(IOP);
+      IsPseudo = true;
+    }
     assert(BundleMember &&
            "no ScheduleData for bundle member (maybe not in same basic block)");
+    assert(!BundleMember->isPartOfBundle() && "Already part of another bundle");
     if (BundleMember->IsScheduled) {
       // A bundle member was scheduled as single instruction before and now
       // needs to be scheduled as part of the bundle. We just get rid of the
       // existing schedule.
       LLVM_DEBUG(dbgs() << "SLP:  reset schedule because " << *BundleMember
                         << " was already scheduled\n");
       ReSchedule = true;
     }
     assert(BundleMember->isSchedulingEntity() &&
            "bundle member already part of other bundle");
     if (PrevInBundle) {
       PrevInBundle->NextInBundle = BundleMember;
     } else {
       Bundle = BundleMember;
     }
     BundleMember->UnscheduledDepsInBundle = 0;
+    BundleMember->Opcode = IOP->MainOpcode;
+    BundleMember->Parent = IOP->getParent();
     Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps;
 
     // Group the instructions to a bundle.
     BundleMember->FirstInBundle = Bundle;
     PrevInBundle = BundleMember;
   }
-  if (ScheduleEnd != OldScheduleEnd) {
+  if (ScheduleEnd != OldScheduleEnd || IsPseudo) {
     // The scheduling region got new instructions at the lower end (or it is a
     // new region for the first bundle). This makes it necessary to
     // recalculate all dependencies.
     // It is seldom that this needs to be done a second time after adding the
     // initial bundle to the region.
     for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
       doForAllOpcodes(I, [](ScheduleData *SD) {
         SD->clearDependencies();
while (!Bundle->isReady() && !ReadyInsts.empty()) {
     ScheduleData *pickedSD = ReadyInsts.back();
     ReadyInsts.pop_back();
 
     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
       schedule(pickedSD, ReadyInsts);
     }
   }
   if (!Bundle->isReady()) {
-    cancelScheduling(VL, S.OpValue);
+    cancelScheduling(IL[0]);
+    // We have to clear all dependencies, since all values
+    // were calculated for the vectorized bundle.
+    for (auto *I = ScheduleStart; I != ScheduleEnd;
+      I = I->getNextNode()) {
+      doForAllOpcodes(I, [](ScheduleData *SD) {
+        SD->clearDependencies();
+      });
+    }
+    resetSchedule();
     return false;
   }
   return true;
 }
 
-void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL,
-                                                Value *OpValue) {
-  if (isa<PHINode>(OpValue))
+void BoUpSLP::BlockScheduling::cancelScheduling(InstructionOrPseudo *IOP) {
+  if (!IOP->MainOp)
     return;
-
-  ScheduleData *Bundle = getScheduleData(OpValue);
+  if (isa<PHINode>(IOP->MainOp))
+    return;
+  auto Key = IOP->getKey();
+  ScheduleData *Bundle = getScheduleData(IOP)->FirstInBundle;
+  assert(Bundle && "Counld not find bundle");
   LLVM_DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
   assert(!Bundle->IsScheduled &&
          "Can't cancel bundle which is already scheduled");
   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
          "tried to unbundle something which is not a bundle");
 
   // Un-bundle: make single instructions out of the bundle.
   ScheduleData *BundleMember = Bundle;
   while (BundleMember) {
-    assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links");
+    assert(BundleMember->FirstInBundle == Bundle && "Corrupt bundle links");
+    assert(BundleMember->Parent == Key.first &&
+           BundleMember->Opcode == Key.second && "Corrupt bundle");
     BundleMember->FirstInBundle = BundleMember;
     ScheduleData *Next = BundleMember->NextInBundle;
     BundleMember->NextInBundle = nullptr;
     BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps;
+    if (BundleMember->IsPseudo) {
+      ScheduleDataMap[BundleMember->Inst].erase(Key);
+      BundleMember->Opcode = 0;
+      BundleMember->Parent = nullptr;
+    } else {
+      BundleMember->Opcode = 0;
+      BundleMember->Parent = nullptr;
       if (BundleMember->UnscheduledDepsInBundle == 0) {
         ReadyInsts.insert(BundleMember);
       }
+    }
     BundleMember = Next;
   }
 }
 
 BoUpSLP::ScheduleData *BoUpSLP::BlockScheduling::allocateScheduleDataChunks() {
   // Allocate a new ScheduleData for the instruction.
   if (ChunkPos >= ChunkSize) {
     ScheduleDataChunks.push_back(llvm::make_unique<ScheduleData[]>(ChunkSize));
     ChunkPos = 0;
   }
   return &(ScheduleDataChunks.back()[ChunkPos++]);
 }
 
-bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V,
-                                                      const InstructionsState &S) {
-  if (getScheduleData(V, isOneOf(S, V)))
+bool BoUpSLP::BlockScheduling::extendSchedulingRegion(
+    InstructionOrPseudo *IOP) {
+  if (getScheduleData(IOP))
     return true;
-  Instruction *I = dyn_cast<Instruction>(V);
-  assert(I && "bundle member must be an instruction");
-  assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled");
-  auto &&CheckSheduleForI = [this, &S](Instruction *I) -> bool {
-    ScheduleData *ISD = getScheduleData(I);
-    if (!ISD)
+  auto *I = IOP->getOpInst();
+  assert(!isa<PHINode>(I)
+         && "phi nodes don't need to be scheduled");
+  auto &&CheckSheduleForI = [this, &IOP](Instruction *I) -> bool {
+    ScheduleData *ISD = ScheduleDataMap[I][std::make_pair(nullptr, 0)];
+    if (!ISD || ISD->SchedulingRegionID != SchedulingRegionID)
       return false;
-    assert(isInSchedulingRegion(ISD) &&
-           "ScheduleData not in scheduling region");
+    if (ISD->isPartOfBundle()) {
       ScheduleData *SD = allocateScheduleDataChunks();
-    SD->Inst = I;
-    SD->init(SchedulingRegionID, S.OpValue);
-    ExtraScheduleDataMap[I][S.OpValue] = SD;
+      SD->init(SchedulingRegionID, ISD, IOP);
+      ScheduleDataMap[I][IOP->getKey()] = SD;
+    }
     return true;
   };
   if (CheckSheduleForI(I))
     return true;
   if (!ScheduleStart) {
     // It's the first instruction in the new region.
     initScheduleData(I, I->getNextNode(), nullptr, nullptr);
     ScheduleStart = I;
     ScheduleEnd = I->getNextNode();
-    if (isOneOf(S, I) != I)
-      CheckSheduleForI(I);
     assert(ScheduleEnd && "tried to vectorize a terminator?");
-    LLVM_DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
+    LLVM_DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I
+               << "\n");
     return true;
   }
   // Search up and down at the same time, because we don't know if the new
   // instruction is above or below the existing scheduling region.
   BasicBlock::reverse_iterator UpIter =
       ++ScheduleStart->getIterator().getReverse();
   BasicBlock::reverse_iterator UpperEnd = BB->rend();
   BasicBlock::iterator DownIter = ScheduleEnd->getIterator();
   BasicBlock::iterator LowerEnd = BB->end();
   while (true) {
     if (++ScheduleRegionSize > ScheduleRegionSizeLimit) {
       LLVM_DEBUG(dbgs() << "SLP:  exceeded schedule region size limit\n");
       return false;
     }
 
     if (UpIter != UpperEnd) {
       if (&*UpIter == I) {
-        initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion);
+        initScheduleData(I, ScheduleStart, nullptr,
+                         FirstLoadStoreInRegion);
         ScheduleStart = I;
-        if (isOneOf(S, I) != I)
-          CheckSheduleForI(I);
-        LLVM_DEBUG(dbgs() << "SLP:  extend schedule region start to " << *I
-                          << "\n");
+        LLVM_DEBUG(dbgs() << "SLP:  extend schedule region start to "
+                          << *I << "\n");
         return true;
       }
       UpIter++;
     }
     if (DownIter != LowerEnd) {
       if (&*DownIter == I) {
-        initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion,
-                         nullptr);
+        initScheduleData(ScheduleEnd, I->getNextNode(),
+                         LastLoadStoreInRegion, nullptr);
         ScheduleEnd = I->getNextNode();
-        if (isOneOf(S, I) != I)
-          CheckSheduleForI(I);
         assert(ScheduleEnd && "tried to vectorize a terminator?");
         LLVM_DEBUG(dbgs() << "SLP:  extend schedule region end to " << *I
                           << "\n");
         return true;
       }
       DownIter++;
     }
     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
            "instruction not found in block");
   }
   return true;
 }
 
-void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
-                                                Instruction *ToI,
-                                                ScheduleData *PrevLoadStore,
-                                                ScheduleData *NextLoadStore) {
+void BoUpSLP::BlockScheduling::initScheduleData(
+    Instruction *FromI, Instruction *ToI, ScheduleData *PrevLoadStore,
   ScheduleData *CurrentLoadStore = PrevLoadStore;
   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
-    ScheduleData *SD = ScheduleDataMap[I];
+    ScheduleData *SD = ScheduleDataMap[I][std::make_pair(nullptr, 0)];
     if (!SD) {
       SD = allocateScheduleDataChunks();
-      ScheduleDataMap[I] = SD;
+      ScheduleDataMap[I][std::make_pair(nullptr, 0)] = SD;
       SD->Inst = I;
     }
     assert(!isInSchedulingRegion(SD) &&
            "new ScheduleData already in scheduling region");
-    SD->init(SchedulingRegionID, I);
+    SD->init(SchedulingRegionID);
 
     if (I->mayReadOrWriteMemory() &&
         (!isa<IntrinsicInst>(I) ||
          cast<IntrinsicInst>(I)->getIntrinsicID() != Intrinsic::sideeffect)) {
       // Update the linked list of memory accessing instructions.
       if (CurrentLoadStore) {
         CurrentLoadStore->NextLoadStore = SD;
       } else {
void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD,
   SmallVector<ScheduleData *, 10> WorkList;
   WorkList.push_back(SD);
 
   while (!WorkList.empty()) {
     ScheduleData *SD = WorkList.back();
     WorkList.pop_back();
 
     ScheduleData *BundleMember = SD;
+    unsigned Opcode = BundleMember->Opcode;
+    Value *Parent = BundleMember->Parent;
     while (BundleMember) {
-      assert(isInSchedulingRegion(BundleMember));
+      assert(isInSchedulingRegion(BundleMember) &&
+             BundleMember->Opcode == Opcode &&
+             BundleMember->Parent == Parent && "Corrupt bundle member");
+
       if (!BundleMember->hasValidDependencies()) {
 
         LLVM_DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember
                           << "\n");
         BundleMember->Dependencies = 0;
         BundleMember->resetUnscheduledDeps();
 
         // Handle def-use chain dependencies.
-        if (BundleMember->OpValue != BundleMember->Inst) {
-          ScheduleData *UseSD = getScheduleData(BundleMember->Inst);
-          if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
-            BundleMember->Dependencies++;
-            ScheduleData *DestBundle = UseSD->FirstInBundle;
-            if (!DestBundle->IsScheduled)
-              BundleMember->incrementUnscheduledDeps(1);
-            if (!DestBundle->hasValidDependencies())
-              WorkList.push_back(DestBundle);
-          }
-        } else {
-          for (User *U : BundleMember->Inst->users()) {
-            if (isa<Instruction>(U)) {
-              ScheduleData *UseSD = getScheduleData(U);
-              if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
-                BundleMember->Dependencies++;
-                ScheduleData *DestBundle = UseSD->FirstInBundle;
-                if (!DestBundle->IsScheduled)
-                  BundleMember->incrementUnscheduledDeps(1);
-                if (!DestBundle->hasValidDependencies())
-                  WorkList.push_back(DestBundle);
-              }
-            } else {
-              // I'm not sure if this can ever happen. But we need to be safe.
-              // This lets the instruction/bundle never be scheduled and
-              // eventually disable vectorization.
-              BundleMember->Dependencies++;
-              BundleMember->incrementUnscheduledDeps(1);
-            }
-          }
-        }
+          if (auto *I = dyn_cast<Instruction>(U)) {
+            doForAllOpcodes(I, [&](ScheduleData *UseSD) {
+            });
 
         // Handle the memory dependencies.
         ScheduleData *DepDest = BundleMember->NextLoadStore;
         if (DepDest) {
           Instruction *SrcInst = BundleMember->Inst;
           MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA);
-          bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
+          bool SrcMayWrite = SrcInst->mayWriteToMemory();
           unsigned numAliased = 0;
           unsigned DistToSrc = 1;
 
           while (DepDest) {
             assert(isInSchedulingRegion(DepDest));
 
             // We have two limits to reduce the complexity:
             // 1) AliasedCheckLimit: It's a small limit to reduce calls to
             //    SLP->isAliased (which is the expensive part in this loop).
             // 2) MaxMemDepDistance: It's for very large blocks and it aborts
             //    the whole loop (even if the loop is fast, it's quadratic).
             //    It's important for the loop break condition (see below) to
             //    check this limit even between two read-only instructions.
             if (DistToSrc >= MaxMemDepDistance ||
                     ((SrcMayWrite || DepDest->Inst->mayWriteToMemory()) &&
                      (numAliased >= AliasedCheckLimit ||
                       SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) {
 
               // We increment the counter only if the locations are aliased
               // (instead of counting all alias checks). This gives a better
               // balance between reduced runtime and accurate dependencies.
               numAliased++;
 
-              DepDest->MemoryDependencies.push_back(BundleMember);
+              doForAllOpcodes(DepDest->Inst, [&](ScheduleData *Dep) {
+                Dep->MemoryDependencies.push_back(BundleMember);
                 BundleMember->Dependencies++;
-              ScheduleData *DestBundle = DepDest->FirstInBundle;
+                ScheduleData *DestBundle = Dep->FirstInBundle;
                 if (!DestBundle->IsScheduled) {
                   BundleMember->incrementUnscheduledDeps(1);
                 }
                 if (!DestBundle->hasValidDependencies()) {
                   WorkList.push_back(DestBundle);
                 }
+              });
             }
             DepDest = DepDest->NextLoadStore;
 
             // Example, explaining the loop break condition: Let's assume our
             // starting instruction is i0 and MaxMemDepDistance = 3.
             //
             //                      +--------v--v--v
             //             i0,i1,i2,i3,i4,i5,i6,i7,i8
while (!WorkList.empty()) {
     }
   }
 }
 
 void BoUpSLP::BlockScheduling::resetSchedule() {
   assert(ScheduleStart &&
          "tried to reset schedule on block which has not been scheduled");
   for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
-    doForAllOpcodes(I, [&](ScheduleData *SD) {
-      assert(isInSchedulingRegion(SD) &&
-             "ScheduleData not in scheduling region");
+    doForAllOpcodes(I, [](ScheduleData *SD) {
       SD->IsScheduled = false;
       SD->resetUnscheduledDeps();
     });
   }
   ReadyInsts.clear();
 }
 
+void BoUpSLP::eliminatePseudos(BlockScheduling *BS) {
+  if (!BS->ScheduleStart)
+    return;
+  bool Changed = false;
+  for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
+       I = I->getNextNode()) {
+    SmallSet<std::pair<Value *, unsigned>, 2> Keys;
+    SmallDenseMap<Instruction *, ScheduleData *> NewOps;
+    BS->doForAllOpcodes(I, [&](ScheduleData *SD) {
+      if (!SD->IsPseudo)
+        return;
+      std::pair<Value *, unsigned> Key = std::make_pair(
+                                                SD->Parent, SD->Opcode);
+      // Remove any pseudo instruction that
+      // remaines after bundles construction.
+      if (!SD->isPartOfBundle()) {
+        Keys.insert(Key);
+        return;
+      }
+      Changed = true;
+
+      // Emitting a real instruction.
+      Builder.SetInsertPoint(I->getNextNode());
+      Instruction *NewOp = nullptr;
+      NewOp = I->clone();
+      BS->BB->getInstList().push_back(NewOp);
+      NewOp->moveAfter(I);
+      LLVM_DEBUG(dbgs() << "SLP: Replace pseudo instruction"
+                        << *I << " with " << *NewOp
+                        << " in " << *SD->FirstInBundle << "\n");
+
+      // Change instruction in ScheduleData.
+      SD->Inst = NewOp;
+      SD->IsPseudo = false;
+
+      // Remove the pseudo instruction from ScheduleDataMap
+      // and add the real instruction.
+      NewOps[NewOp] = SD;
+      Keys.insert(Key);
+      int Idx = ScalarToTreeEntry[I][Key];
+      ScalarToTreeEntry[NewOp][Key] = Idx;
+      ScalarToTreeEntry[I].erase(Key);
+      TreeEntry *E = &VectorizableTree[Idx];
+      llvm::propagateIRFlags(NewOp, E->Scalars[0]->MainOp);
+      propagateMetadata(NewOp, E->Scalars);
+
+      // Replace instruction in TreeEntry.
+      for (auto *IOP : E->Scalars) {
+        if (IOP->getOpInst() == I)
+          IOP->replaceWith(NewOp);
+      }
+    });
+    for (auto Key : Keys)
+      BS->ScheduleDataMap[I].erase(Key);
+    for (auto Ops : NewOps) {
+      auto *SD = Ops.second;
+      BS->ScheduleDataMap[Ops.first][std::make_pair(SD->Parent, SD->Opcode)] =
+          SD;
+    }
+  }
+
+  // We have to recalulate all dependancies in
+  // the scheduling region if any pseudo instructions
+  // were replaced.
+  if (Changed) {
+    BS->resetSchedule();
+    BS->initialFillReadyList(BS->ReadyInsts);
+    for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
+         I = I->getNextNode()) {
+      if (BS->ScheduleDataMap.find(I) == BS->ScheduleDataMap.end())
+        continue;
+      BS->doForAllOpcodes(I, [&](ScheduleData *SD) {
+        SD->clearDependencies();
+      });
+    }
+  }
+}
+
 void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
   if (!BS->ScheduleStart)
     return;
 
   LLVM_DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n");
 
   BS->resetSchedule();
 
void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
 
   // Ensure that all dependency data is updated and fill the ready-list with
   // initial instructions.
   int Idx = 0;
   int NumToSchedule = 0;
   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
        I = I->getNextNode()) {
     BS->doForAllOpcodes(I, [this, &Idx, &NumToSchedule, BS](ScheduleData *SD) {
+      std::pair<Value *, unsigned> Key = std::make_pair(SD->Parent, SD->Opcode);
       assert(SD->isPartOfBundle() ==
-                 (getTreeEntry(SD->Inst) != nullptr) &&
+                 (ScalarToTreeEntry.find(SD->Inst) != ScalarToTreeEntry.end() &&
+                  ScalarToTreeEntry[SD->Inst].find(Key) !=
+                  ScalarToTreeEntry[SD->Inst].end()) &&
              "scheduler and vectorizer bundle mismatch");
       SD->FirstInBundle->SchedulingPriority = Idx++;
       if (SD->isSchedulingEntity()) {
         BS->calculateDependencies(SD, false, this);
         NumToSchedule++;
       }
     });
   }
   BS->initialFillReadyList(ReadyInsts);
 
   Instruction *LastScheduledInst = BS->ScheduleEnd;
 
   // Do the "real" scheduling.
   while (!ReadyInsts.empty()) {
     ScheduleData *picked = *ReadyInsts.begin();
     ReadyInsts.erase(ReadyInsts.begin());
 
     // Move the scheduled instruction(s) to their dedicated places, if not
     // there yet.
     ScheduleData *BundleMember = picked;
+    unsigned Opcode = BundleMember->Opcode;
+    Value *Parent = BundleMember->Parent;
     while (BundleMember) {
-      Instruction *pickedInst = BundleMember->Inst;
-      if (LastScheduledInst->getNextNode() != pickedInst) {
-        BS->BB->getInstList().remove(pickedInst);
+      assert(Opcode == BundleMember->Opcode &&
+             Parent == BundleMember->Parent && "Corrupt bundle member");
+      Instruction *PickedInst = BundleMember->Inst;
+      if (LastScheduledInst != PickedInst) {
+        BS->BB->getInstList().remove(PickedInst);
         BS->BB->getInstList().insert(LastScheduledInst->getIterator(),
-                                     pickedInst);
+                                     PickedInst);
       }
-      LastScheduledInst = pickedInst;
+      LastScheduledInst = PickedInst;
       BundleMember = BundleMember->NextInBundle;
     }
-
     BS->schedule(picked, ReadyInsts);
     NumToSchedule--;
   }
+#ifndef NDEBUG
+  if (NumToSchedule != 0) {
+    for (BasicBlock::iterator I = BS->BB->begin(), E = BS->BB->end(); I != E;
+         ++I) {
+      BS->doForAllOpcodes(&*I, [](ScheduleData *SD) {
+        LLVM_DEBUG(dbgs() << "SLP: Failed to schedule: " << *SD << "\n");
+      });
+    }
+  }
+#endif
   assert(NumToSchedule == 0 && "could not schedule all instructions");
 
   // Avoid duplicate scheduling of the block.
   BS->ScheduleStart = nullptr;
 }
 
 unsigned BoUpSLP::getVectorElementSize(Value *V) {
   // If V is a store, just return the width of the stored value without

 void BoUpSLP::computeMinimumValueSizes() {
   // If there are no external uses, the expression tree must be rooted by a
   // store. We can't demote in-memory values, so there is nothing to do here.
   if (ExternalUses.empty())
     return;
 
   // We only attempt to truncate integer expressions.
   auto &TreeRoot = VectorizableTree[0].Scalars;
-  auto *TreeRootIT = dyn_cast<IntegerType>(TreeRoot[0]->getType());
+  auto *TreeRootIT = dyn_cast<IntegerType>(TreeRoot[0]->getOp()->getType());
   if (!TreeRootIT)
     return;
 
   // If the expression is not rooted by a store, these roots should have
   // external uses. We will rely on InstCombine to rewrite the expression in
   // the narrower type. However, InstCombine only rewrites single-use values.
   // This means that if a tree entry other than a root is used externally, it
   // must have multiple uses and InstCombine will not rewrite it. The code
   // below ensures that only the roots are used externally.
-  SmallPtrSet<Value *, 32> Expr(TreeRoot.begin(), TreeRoot.end());
+  SmallPtrSet<Value *, 32> Expr;
+  for (auto *IOP : TreeRoot)
+    Expr.insert(IOP->getOp());
   for (auto &EU : ExternalUses)
     if (!Expr.erase(EU.Scalar))
       return;
   if (!Expr.empty())
     return;
 
   // Collect the scalar values of the vectorizable expression. We will use this
   // context to determine which values can be demoted. If we see a truncation,
   // we mark it as seeding another demotion.
   for (auto &Entry : VectorizableTree)
-    Expr.insert(Entry.Scalars.begin(), Entry.Scalars.end());
+    for (auto *IOP: Entry.Scalars)
+      Expr.insert(IOP->getOp());
 
   // Ensure the roots of the vectorizable tree don't form a cycle. They must
   // have a single external user that is not in the vectorizable tree.
-  for (auto *Root : TreeRoot)
-    if (!Root->hasOneUse() || Expr.count(*Root->user_begin()))
+  for (auto *Root : TreeRoot) {
+    Value *V = Root->getOp();
+    if (!V->hasOneUse() || Expr.count(*V->user_begin()))
       return;
+  }
 
   // Conservatively determine if we can actually truncate the roots of the
   // expression. Collect the values that can be demoted in ToDemote and
   // additional roots that require investigating in Roots.
   SmallVector<Value *, 32> ToDemote;
   SmallVector<Value *, 4> Roots;
   for (auto *Root : TreeRoot)
-    if (!collectValuesToDemote(Root, Expr, ToDemote, Roots))
+    if (!collectValuesToDemote(Root->getOp(), Expr, ToDemote, Roots))
       return;
 
   // The maximum bit width required to represent all the values that can be
   // demoted without loss of precision. It would be safe to truncate the roots
   // of the expression to this width.
   auto MaxBitWidth = 8u;
 
   // We first check if all the bits of the roots are demanded. If they're not,
   // we can truncate the roots to this narrower type.
   for (auto *Root : TreeRoot) {
-    auto Mask = DB->getDemandedBits(cast<Instruction>(Root));
+    auto Mask = DB->getDemandedBits(Root->getOpInst());
     MaxBitWidth = std::max<unsigned>(
         Mask.getBitWidth() - Mask.countLeadingZeros(), MaxBitWidth);
   }
 
   // True if the roots can be zero-extended back to their original type, rather
   // than sign-extended. We know that if the leading bits are not demanded, we
   // can safely zero-extend. So we initialize IsKnownPositive to True.
   bool IsKnownPositive = true;
 
   // If all the bits of the roots are demanded, we can try a little harder to
   // compute a narrower type. This can happen, for example, if the roots are
   // getelementptr indices. InstCombine promotes these indices to the pointer
   // width. Thus, all their bits are technically demanded even though the
   // address computation might be vectorized in a smaller type.
   //
   // We start by looking at each entry that can be demoted. We compute the
   // maximum bit width required to store the scalar by using ValueTracking to
   // compute the number of high-order bits we can truncate.
-  if (MaxBitWidth == DL->getTypeSizeInBits(TreeRoot[0]->getType()) &&
-      llvm::all_of(TreeRoot, [](Value *R) {
-        assert(R->hasOneUse() && "Root should have only one use!");
-        return isa<GetElementPtrInst>(R->user_back());
+  if (MaxBitWidth == DL->getTypeSizeInBits(TreeRoot[0]->getOp()->getType()) &&
+      llvm::all_of(TreeRoot, [](InstructionOrPseudo *R) {
+        Value *V = R->getOp();
+        assert(V->hasOneUse() && "Root should have only one use!");
+        return isa<GetElementPtrInst>(V->user_back());
       })) {
     MaxBitWidth = 8u;
 
     // Determine if the sign bit of all the roots is known to be zero. If not,
     // IsKnownPositive is set to False.
-    IsKnownPositive = llvm::all_of(TreeRoot, [&](Value *R) {
-      KnownBits Known = computeKnownBits(R, *DL);
+    IsKnownPositive = llvm::all_of(TreeRoot, [&](InstructionOrPseudo *R) {
+      KnownBits Known = computeKnownBits(R->getOp(), *DL);
       return Known.isNonNegative();
     });
 
     // Determine the maximum number of bits required to store the scalar
     // values.
     for (auto *Scalar : ToDemote) {
       auto NumSignBits = ComputeNumSignBits(Scalar, *DL, 0, AC, nullptr, DT);
       auto NumTypeBits = DL->getTypeSizeInBits(Scalar->getType());
bool SLPVectorizerPass::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
   if (VL.size() < 2)
     return false;
 
   LLVM_DEBUG(dbgs() << "SLP: Trying to vectorize a list of length = "
                     << VL.size() << ".\n");
 
   // Check that all of the parts are scalar instructions of the same type,
   // we permit an alternate opcode via InstructionsState.
-  InstructionsState S = getSameOpcode(VL);
+  SmallVector<InstructionOrPseudo, 4> ArrayIL;
+  SmallVector<InstructionOrPseudo *, 4> IL;
+
+  for (Value *V: VL)
+    ArrayIL.push_back(InstructionOrPseudo(VL[0], V));
+  for (unsigned idx=0; idx < ArrayIL.size(); idx++)
+    IL.push_back(&ArrayIL[idx]);
+  InstructionsState S = getSameOpcode(IL);
   if (!S.getOpcode())
     return false;
 
   Instruction *I0 = cast<Instruction>(S.OpValue);
   unsigned Sz = R.getVectorElementSize(I0);
   unsigned MinVF = std::max(2U, R.getMinVecRegSize() / Sz);
   unsigned MaxVF = std::max<unsigned>(PowerOf2Floor(VL.size()), MinVF);
   if (MaxVF < 2) {

test/Transforms/SLPVectorizer/X86/duplicate.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -slp-vectorizer -S -mtriple=x86_64-unknown-linux-gnu -mcpu=bdver2 < %s | FileCheck %s
+
+; Reusing %sub.i1247 operation in two different bundles.
+
+%class.j = type { %class.c* }
+%class.c = type { [3 x double] }
+
+@h = dso_local local_unnamed_addr global i64 0, align 8
+@i = dso_local local_unnamed_addr global i64 0, align 8
+
+; Function Attrs: uwtable
+define dso_local void @foo(%class.j* nocapture readonly %this) local_unnamed_addr #0 align 2 personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+; CHECK-LABEL: @foo(
+; CHECK-NEXT:  invoke.cont18:
+; CHECK-NEXT:    [[M:%.*]] = alloca [[CLASS_C:%.*]], align 8
+; CHECK-NEXT:    [[AGG_TMP:%.*]] = alloca [[CLASS_C]], align 8
+; CHECK-NEXT:    [[TMP0:%.*]] = bitcast %class.c* [[M]] to i8*
+; CHECK-NEXT:    call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull [[TMP0]])
+; CHECK-NEXT:    [[L:%.*]] = getelementptr inbounds [[CLASS_J:%.*]], %class.j* [[THIS:%.*]], i64 0, i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = load %class.c*, %class.c** [[L]], align 8
+; CHECK-NEXT:    [[TMP2:%.*]] = load i64, i64* @h, align 8
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[TMP1]], i64 [[TMP2]], i32 0, i64 0
+; CHECK-NEXT:    [[ARRAYIDX5_I49:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[TMP1]], i64 [[TMP2]], i32 0, i64 1
+; CHECK-NEXT:    [[ARRAYIDX9_I51:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[TMP1]], i64 [[TMP2]], i32 0, i64 2
+; CHECK-NEXT:    [[TMP4:%.*]] = load double, double* [[ARRAYIDX9_I51]], align 8
+; CHECK-NEXT:    [[TMP5:%.*]] = load i64, i64* @i, align 8
+; CHECK-NEXT:    [[ARRAYIDX_I41:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[TMP1]], i64 [[TMP5]], i32 0, i64 0
+; CHECK-NEXT:    [[ARRAYIDX5_I44:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[TMP1]], i64 [[TMP5]], i32 0, i64 1
+; CHECK-NEXT:    [[TMP6:%.*]] = bitcast double* [[ARRAYIDX_I41]] to <2 x double>*
+; CHECK-NEXT:    [[TMP7:%.*]] = load <2 x double>, <2 x double>* [[TMP6]], align 8
+; CHECK-NEXT:    [[TMP8:%.*]] = bitcast double* [[TMP3]] to <2 x double>*
+; CHECK-NEXT:    [[TMP9:%.*]] = load <2 x double>, <2 x double>* [[TMP8]], align 8
+; CHECK-NEXT:    [[TMP10:%.*]] = fsub fast <2 x double> [[TMP7]], [[TMP9]]
+; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <2 x double> [[TMP9]], i32 0
+; CHECK-NEXT:    [[TMP12:%.*]] = insertelement <2 x double> undef, double [[TMP11]], i32 0
+; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <2 x double> [[TMP7]], i32 0
+; CHECK-NEXT:    [[TMP14:%.*]] = insertelement <2 x double> [[TMP12]], double [[TMP13]], i32 1
+; CHECK-NEXT:    [[TMP15:%.*]] = insertelement <2 x double> <double 2.000000e+00, double undef>, double [[TMP11]], i32 1
+; CHECK-NEXT:    [[TMP16:%.*]] = fmul fast <2 x double> [[TMP14]], [[TMP15]]
+; CHECK-NEXT:    [[TMP17:%.*]] = fsub fast <2 x double> [[TMP14]], [[TMP15]]
+; CHECK-NEXT:    [[TMP18:%.*]] = shufflevector <2 x double> [[TMP16]], <2 x double> [[TMP17]], <2 x i32> <i32 0, i32 3>
+; CHECK-NEXT:    [[TMP19:%.*]] = insertelement <2 x double> undef, double [[TMP4]], i32 0
+; CHECK-NEXT:    [[TMP20:%.*]] = insertelement <2 x double> [[TMP19]], double [[TMP11]], i32 1
+; CHECK-NEXT:    [[TMP21:%.*]] = fmul fast <2 x double> [[TMP10]], [[TMP20]]
+; CHECK-NEXT:    [[TMP22:%.*]] = fsub fast <2 x double> [[TMP21]], [[TMP18]]
+; CHECK-NEXT:    [[P_SROA_0_0__SROA_CAST65:%.*]] = bitcast %class.c* [[AGG_TMP]] to i64*
+; CHECK-NEXT:    store i64 4607182418800017408, i64* [[P_SROA_0_0__SROA_CAST65]], align 8
+; CHECK-NEXT:    [[P_SROA_5_0__SROA_IDX68:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[AGG_TMP]], i64 0, i32 0, i64 1
+; CHECK-NEXT:    [[P_SROA_6_0__SROA_IDX72:%.*]] = getelementptr inbounds [[CLASS_C]], %class.c* [[AGG_TMP]], i64 0, i32 0, i64 2
+; CHECK-NEXT:    [[TMP23:%.*]] = bitcast double* [[P_SROA_5_0__SROA_IDX68]] to <2 x double>*
+; CHECK-NEXT:    store <2 x double> [[TMP22]], <2 x double>* [[TMP23]], align 8
+; CHECK-NEXT:    invoke void @bar(%class.c* nonnull [[M]], %class.c* nonnull [[AGG_TMP]])
+; CHECK-NEXT:    to label [[INVOKE_CONT24:%.*]] unwind label [[LPAD23:%.*]]
+; CHECK:       invoke.cont24:
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull [[TMP0]])
+; CHECK-NEXT:    ret void
+; CHECK:       lpad23:
+; CHECK-NEXT:    [[TMP24:%.*]] = landingpad { i8*, i32 }
+; CHECK-NEXT:    cleanup
+; CHECK-NEXT:    call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull [[TMP0]])
+; CHECK-NEXT:    resume { i8*, i32 } [[TMP24]]
+;
+invoke.cont18:
+  %m = alloca %class.c, align 8
+  %agg.tmp = alloca %class.c, align 8
+  %0 = bitcast %class.c* %m to i8*
+  call void @llvm.lifetime.start.p0i8(i64 24, i8* nonnull %0) #3
+  %l = getelementptr inbounds %class.j, %class.j* %this, i64 0, i32 0
+  %1 = load %class.c*, %class.c** %l, align 8
+  %2 = load i64, i64* @h, align 8
+  %3 = getelementptr inbounds %class.c, %class.c* %1, i64 %2, i32 0, i64 0
+  %4 = load double, double* %3, align 8
+  %arrayidx5.i49 = getelementptr inbounds %class.c, %class.c* %1, i64 %2, i32 0, i64 1
+  %arrayidx9.i51 = getelementptr inbounds %class.c, %class.c* %1, i64 %2, i32 0, i64 2
+  %5 = load double, double* %arrayidx9.i51, align 8
+  %6 = load i64, i64* @i, align 8
+  %arrayidx.i41 = getelementptr inbounds %class.c, %class.c* %1, i64 %6, i32 0, i64 0
+  %7 = load double, double* %arrayidx.i41, align 8
+  %sub.i43 = fsub fast double %7, %4
+  %arrayidx5.i44 = getelementptr inbounds %class.c, %class.c* %1, i64 %6, i32 0, i64 1
+  %8 = load double, double* %arrayidx5.i44, align 8
+  %9 = load double, double* %arrayidx5.i49, align 8
+  %sub8.i = fsub fast double %8, %9
+  %mul.i = fmul fast double %sub.i43, %5
+  %mul8.i = fmul fast double %4, 2.000000e+00
+  %sub.i = fsub fast double %mul.i, %mul8.i
+  %mul13.i = fmul fast double %sub8.i, %4
+  %sub16.i = fsub fast double %mul13.i, %sub.i43
+  %p.sroa.0.0..sroa_cast65 = bitcast %class.c* %agg.tmp to i64*
+  store i64 4607182418800017408, i64* %p.sroa.0.0..sroa_cast65, align 8
+  %p.sroa.5.0..sroa_idx68 = getelementptr inbounds %class.c, %class.c* %agg.tmp, i64 0, i32 0, i64 1
+  store double %sub.i, double* %p.sroa.5.0..sroa_idx68, align 8
+  %p.sroa.6.0..sroa_idx72 = getelementptr inbounds %class.c, %class.c* %agg.tmp, i64 0, i32 0, i64 2
+  store double %sub16.i, double* %p.sroa.6.0..sroa_idx72, align 8
+  invoke void @bar(%class.c* nonnull %m, %class.c* nonnull %agg.tmp)
+  to label %invoke.cont24 unwind label %lpad23
+
+invoke.cont24:                                    ; preds = %invoke.cont18
+  call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull %0) #3
+  ret void
+
+lpad23:                                           ; preds = %invoke.cont18
+  %10 = landingpad { i8*, i32 }
+  cleanup
+  call void @llvm.lifetime.end.p0i8(i64 24, i8* nonnull %0) #3
+  resume { i8*, i32 } %10
+}
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) #1
+
+declare dso_local i32 @__gxx_personality_v0(...)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) #1
+
+declare dso_local void @bar(%class.c*, %class.c*) local_unnamed_addr #2