Lines Matching defs:TreeEntry
1337 struct TreeEntry;
1427 const TreeEntry &Root = *VectorizableTree.front().get();
1428 if (Root.State != TreeEntry::Vectorize || Root.isAltShuffle() ||
1527 std::optional<OrdersType> findReusedOrderedScalars(const TreeEntry &TE);
1530 std::optional<OrdersType> findPartiallyOrderedLoads(const TreeEntry &TE);
1539 std::optional<OrdersType> getReorderingData(const TreeEntry &TE,
1657 /// (i) the user TreeEntry index, and
1661 EdgeInfo(TreeEntry *UserTE, unsigned EdgeIdx)
1663 /// The user TreeEntry.
1664 TreeEntry *UserTE = nullptr;
1778 if (ArrayRef<TreeEntry *> TEs1 = R.getTreeEntries(V1); !TEs1.empty()) {
1779 SmallPtrSet<TreeEntry *, 4> Set(TEs1.begin(), TEs1.end());
1780 if (ArrayRef<TreeEntry *> TEs2 = R.getTreeEntries(V2);
1782 any_of(TEs2, [&](TreeEntry *E) { return Set.contains(E); }))
2857 ArrayRef<TreeEntry *> Entries = getTreeEntries(I);
2862 (Entries.empty() || none_of(Entries, [&](const TreeEntry *Entry) {
2974 const TreeEntry &E, bool IsProfitableToDemoteRoot, unsigned &BitWidth,
2975 SmallVectorImpl<unsigned> &ToDemote, DenseSet<const TreeEntry *> &Visited,
2987 canReorderOperands(TreeEntry *UserTE,
2988 SmallVectorImpl<std::pair<unsigned, TreeEntry *>> &Edges,
2989 ArrayRef<TreeEntry *> ReorderableGathers,
2990 SmallVectorImpl<TreeEntry *> &GatherOps);
2994 void reorderNodeWithReuses(TreeEntry &TE, ArrayRef<int> Mask) const;
2998 TreeEntry *getVectorizedOperand(TreeEntry *UserTE, unsigned OpIdx) {
3000 TreeEntry *TE = nullptr;
3002 for (TreeEntry *E : getTreeEntries(V)) {
3019 const TreeEntry *getVectorizedOperand(const TreeEntry *UserTE,
3022 const_cast<TreeEntry *>(UserTE), OpIdx);
3035 const TreeEntry *getOperandEntry(const TreeEntry *E, unsigned Idx) const;
3040 Instruction *getRootEntryInstruction(const TreeEntry &Entry) const;
3044 getCastContextHint(const TreeEntry &TE) const;
3047 InstructionCost getEntryCost(const TreeEntry *E,
3069 Value *vectorizeTree(TreeEntry *E, bool PostponedPHIs);
3073 TreeEntry *getMatchedVectorizedOperand(const TreeEntry *E, unsigned NodeIdx);
3074 const TreeEntry *getMatchedVectorizedOperand(const TreeEntry *E,
3083 Value *vectorizeOperand(TreeEntry *E, unsigned NodeIdx, bool PostponedPHIs);
3089 ResTy processBuildVector(const TreeEntry *E, Type *ScalarTy, Args &...Params);
3094 Value *createBuildVector(const TreeEntry *E, Type *ScalarTy,
3101 Instruction &getLastInstructionInBundle(const TreeEntry *E);
3134 const TreeEntry *TE, ArrayRef<Value *> VL, MutableArrayRef<int> Mask,
3135 SmallVectorImpl<const TreeEntry *> &Entries, unsigned Part,
3151 const TreeEntry *TE, ArrayRef<Value *> VL, SmallVectorImpl<int> &Mask,
3152 SmallVectorImpl<SmallVector<const TreeEntry *>> &Entries,
3163 void setInsertPointAfterBundle(const TreeEntry *E);
3187 collectUserStores(const BoUpSLP::TreeEntry *TE) const;
3203 findExternalStoreUsersReorderIndices(TreeEntry *TE) const;
3207 void reorderGatherNode(TreeEntry &TE);
3209 struct TreeEntry {
3210 using VecTreeTy = SmallVector<std::unique_ptr<TreeEntry>, 8>;
3211 TreeEntry(VecTreeTy &Container) : Container(Container) {}
3258 bool hasEqualOperands(const TreeEntry &TE) const {
3336 /// The TreeEntry index containing the user of this entry. We can actually
3392 /// \returns the \p OpIdx operand of this TreeEntry.
3398 /// \returns the \p OpIdx operand of this TreeEntry.
3578 void dumpTreeCosts(const TreeEntry *E, InstructionCost ReuseShuffleCost,
3593 TreeEntry *newTreeEntry(ArrayRef<Value *> VL,
3600 TreeEntry::EntryState EntryState =
3601 Bundle ? TreeEntry::Vectorize : TreeEntry::NeedToGather;
3602 TreeEntry *E = newTreeEntry(VL, EntryState, Bundle, S, UserTreeIdx,
3609 TreeEntry *newTreeEntry(ArrayRef<Value *> VL,
3610 TreeEntry::EntryState EntryState,
3616 assert(((!Bundle && EntryState == TreeEntry::NeedToGather) ||
3617 (Bundle && EntryState != TreeEntry::NeedToGather)) &&
3621 EntryState == TreeEntry::NeedToGather && S &&
3625 VectorizableTree.push_back(std::make_unique<TreeEntry>(VectorizableTree));
3626 TreeEntry *Last = VectorizableTree.back().get();
3675 // Update the scheduler bundle to point to this TreeEntry.
3716 TreeEntry::VecTreeTy VectorizableTree;
3729 ArrayRef<TreeEntry *> getTreeEntries(Value *V) const {
3738 TreeEntry *getSameValuesTreeEntry(Value *V, ArrayRef<Value *> VL,
3741 for (TreeEntry *TE : ScalarToTreeEntries.lookup(V))
3758 TreeEntry::EntryState
3765 SmallDenseMap<Value *, SmallVector<TreeEntry *>> ScalarToTreeEntries;
3782 DenseMap<const TreeEntry *, Instruction *> EntryToLastInstruction;
3787 SetVector<const TreeEntry *> PostponedGathers;
3790 DenseMap<Value *, SmallPtrSet<const TreeEntry *, 4>>;
3806 ExternalUser(Value *S, llvm::User *U, const TreeEntry &E, int L)
3816 const TreeEntry &E;
4020 /// The TreeEntry that this instruction corresponds to.
4021 TreeEntry *TE = nullptr;
4171 // through the TreeEntry.
4172 if (TreeEntry *TE = BundleMember->TE) {
4189 "Missed TreeEntry operands?");
4418 DenseMap<const TreeEntry *, std::pair<uint64_t, bool>> MinBWs;
4440 using TreeEntry = BoUpSLP::TreeEntry;
4443 using NodeRef = TreeEntry *;
4445 using ContainerTy = BoUpSLP::TreeEntry::VecTreeTy;
4448 /// TreeEntry pointers.
4473 /// For the node iterator we just need to turn the TreeEntry iterator into a
4474 /// TreeEntry* iterator so that it dereferences to NodeRef.
4501 using TreeEntry = BoUpSLP::TreeEntry;
4505 std::string getNodeLabel(const TreeEntry *Entry, const BoUpSLP *R) {
4522 static std::string getNodeAttributes(const TreeEntry *Entry,
4526 if (Entry->State == TreeEntry::ScatterVectorize ||
4527 Entry->State == TreeEntry::StridedVectorize)
4635 BoUpSLP::findReusedOrderedScalars(const BoUpSLP::TreeEntry &TE) {
4648 SmallVector<SmallVector<const TreeEntry *>> Entries;
5484 BoUpSLP::findPartiallyOrderedLoads(const BoUpSLP::TreeEntry &TE) {
5560 BoUpSLP::getReorderingData(const TreeEntry &TE, bool TopToBottom) {
5682 if (TE.State == TreeEntry::StridedVectorize && !TopToBottom &&
5689 if ((TE.State == TreeEntry::Vectorize ||
5690 TE.State == TreeEntry::StridedVectorize) &&
5697 if (TE.State == TreeEntry::Vectorize && TE.getOpcode() == Instruction::PHI) {
5897 void BoUpSLP::reorderNodeWithReuses(TreeEntry &TE, ArrayRef<int> Mask) const {
5948 DenseMap<unsigned, SetVector<TreeEntry *>> VFToOrderedEntries;
5951 DenseMap<const TreeEntry *, OrdersType> GathersToOrders;
5954 DenseMap<const TreeEntry *, OrdersType> PhisToOrders;
5958 DenseMap<const TreeEntry *, OrdersType> AltShufflesToOrders;
5960 // Maps a TreeEntry to the reorder indices of external users.
5961 DenseMap<const TreeEntry *, SmallVector<OrdersType, 1>>
5967 const std::unique_ptr<TreeEntry> &TE) {
6004 const TreeEntry *UserTE = TE.get();
6009 return EI.UserTE->State == TreeEntry::Vectorize &&
6017 if (!(TE->State == TreeEntry::Vectorize ||
6018 TE->State == TreeEntry::StridedVectorize) ||
6021 if (TE->State == TreeEntry::Vectorize &&
6036 ArrayRef<TreeEntry *> OrderedEntries = It->second.getArrayRef();
6045 SmallPtrSet<const TreeEntry *, 4> VisitedOps;
6046 for (const TreeEntry *OpTE : OrderedEntries) {
6064 if (OpTE->State == TreeEntry::Vectorize &&
6091 if (OpTE->State == TreeEntry::Vectorize &&
6152 for (std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
6189 if ((TE->State == TreeEntry::Vectorize ||
6190 TE->State == TreeEntry::StridedVectorize) &&
6224 TreeEntry *UserTE, SmallVectorImpl<std::pair<unsigned, TreeEntry *>> &Edges,
6225 ArrayRef<TreeEntry *> ReorderableGathers,
6226 SmallVectorImpl<TreeEntry *> &GatherOps) {
6228 if (any_of(Edges, [I](const std::pair<unsigned, TreeEntry *> &OpData) {
6230 (OpData.second->State == TreeEntry::Vectorize ||
6231 OpData.second->State == TreeEntry::StridedVectorize);
6234 if (TreeEntry *TE = getVectorizedOperand(UserTE, I)) {
6247 if (TE->State != TreeEntry::Vectorize &&
6248 TE->State != TreeEntry::StridedVectorize &&
6253 TreeEntry *Gather = nullptr;
6255 [&Gather, UserTE, I](TreeEntry *TE) {
6256 assert(TE->State != TreeEntry::Vectorize &&
6257 TE->State != TreeEntry::StridedVectorize &&
6279 SetVector<TreeEntry *> OrderedEntries;
6280 DenseSet<const TreeEntry *> GathersToOrders;
6284 SmallVector<TreeEntry *> NonVectorized;
6285 for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
6286 if (TE->State != TreeEntry::Vectorize &&
6287 TE->State != TreeEntry::StridedVectorize)
6292 if (!(TE->State == TreeEntry::Vectorize ||
6293 TE->State == TreeEntry::StridedVectorize) ||
6303 SmallPtrSet<const TreeEntry *, 4> Visited;
6307 DenseMap<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users;
6308 SmallVector<TreeEntry *> Filtered;
6309 for (TreeEntry *TE : OrderedEntries) {
6310 if (!(TE->State == TreeEntry::Vectorize ||
6311 TE->State == TreeEntry::StridedVectorize ||
6328 for (TreeEntry *TE : Filtered)
6331 std::pair<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>>>
6338 SmallVector<TreeEntry *> GatherOps;
6341 for (const std::pair<unsigned, TreeEntry *> &Op : Data.second)
6353 SmallPtrSet<const TreeEntry *, 4> VisitedOps;
6354 SmallPtrSet<const TreeEntry *, 4> VisitedUsers;
6356 TreeEntry *OpTE = Op.second;
6372 Data.second, [OpTE](const std::pair<unsigned, TreeEntry *> &P) {
6376 if (OpTE->State == TreeEntry::Vectorize &&
6395 const auto AllowsReordering = [&](const TreeEntry *TE) {
6397 (TE->State == TreeEntry::Vectorize && TE->isAltShuffle()) ||
6410 TreeEntry *UserTE = EI.UserTE;
6423 ArrayRef<std::pair<unsigned, TreeEntry *>> Ops = Users[UserTE];
6426 const std::pair<unsigned, TreeEntry *> &Op) {
6437 for (const std::pair<unsigned, TreeEntry *> &Op : Data.second)
6467 for (const std::pair<unsigned, TreeEntry *> &Op : Data.second)
6481 for (const std::pair<unsigned, TreeEntry *> &Op : Data.second) {
6482 TreeEntry *TE = Op.second;
6491 if (TE->State != TreeEntry::Vectorize &&
6492 TE->State != TreeEntry::StridedVectorize &&
6493 (TE->State != TreeEntry::ScatterVectorize ||
6504 for (TreeEntry *Gather : GatherOps) {
6517 if (Data.first->State != TreeEntry::Vectorize ||
6524 Data.first->State == TreeEntry::StridedVectorize) {
6546 Instruction *BoUpSLP::getRootEntryInstruction(const TreeEntry &Entry) const {
6549 Entry.State == TreeEntry::StridedVectorize &&
6560 TreeEntry *Entry = TEPtr.get();
6598 if (ArrayRef<TreeEntry *> UseEntries = getTreeEntries(U);
6603 if (any_of(UseEntries, [&](TreeEntry *UseEntry) {
6604 return UseEntry->State == TreeEntry::ScatterVectorize ||
6612 [](TreeEntry *UseEntry) {
6641 BoUpSLP::collectUserStores(const BoUpSLP::TreeEntry *TE) const {
6758 BoUpSLP::findExternalStoreUsersReorderIndices(TreeEntry *TE) const {
6764 // the current TreeEntry.
7046 for (const TreeEntry *UTE : getTreeEntries(U)) {
7064 [=](const TreeEntry *TE) {
7226 DenseMap<const TreeEntry *, unsigned> EntryToPosition;
7227 SmallPtrSet<const TreeEntry *, 8> DeinterleavedNodes;
7229 for (const TreeEntry *E : ValueToGatherNodes.at(V)) {
7393 const TreeEntry &E = *VectorizableTree[Idx];
7637 BoUpSLP::TreeEntry::EntryState BoUpSLP::getScalarsVectorizationState(
7651 return TreeEntry::NeedToGather;
7662 return TreeEntry::NeedToGather;
7667 return TreeEntry::Vectorize;
7675 return TreeEntry::NeedToGather;
7677 return TreeEntry::Vectorize;
7679 return TreeEntry::NeedToGather;
7697 return TreeEntry::NeedToGather;
7707 return TreeEntry::NeedToGather;
7710 return TreeEntry::Vectorize;
7721 return TreeEntry::Vectorize;
7726 return TreeEntry::NeedToGather;
7728 return TreeEntry::ScatterVectorize;
7733 return TreeEntry::NeedToGather;
7735 return TreeEntry::StridedVectorize;
7751 return TreeEntry::NeedToGather;
7775 return TreeEntry::NeedToGather;
7778 return TreeEntry::Vectorize;
7793 return TreeEntry::NeedToGather;
7796 return TreeEntry::Vectorize;
7824 return TreeEntry::NeedToGather;
7825 return TreeEntry::Vectorize;
7834 return TreeEntry::NeedToGather;
7848 return TreeEntry::NeedToGather;
7867 return TreeEntry::NeedToGather;
7871 return TreeEntry::Vectorize;
7881 return TreeEntry::NeedToGather;
7889 return TreeEntry::NeedToGather;
7909 return TreeEntry::Vectorize;
7913 return TreeEntry::NeedToGather;
7921 return TreeEntry::NeedToGather;
7935 return TreeEntry::NeedToGather;
7952 return TreeEntry::NeedToGather;
7963 return TreeEntry::NeedToGather;
7974 return TreeEntry::NeedToGather;
7978 return TreeEntry::Vectorize;
7984 return TreeEntry::Vectorize;
7988 return TreeEntry::NeedToGather;
7995 return TreeEntry::NeedToGather;
7998 return TreeEntry::Vectorize;
8002 return TreeEntry::NeedToGather;
8188 for (TreeEntry *E : getTreeEntries(S.getMainOp())) {
8306 UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize;
8416 TreeEntry::EntryState State = getScalarsVectorizationState(
8418 if (State == TreeEntry::NeedToGather) {
8453 auto CreateOperandNodes = [&](TreeEntry *TE, const auto &Operands) {
8473 TreeEntry *TE =
8475 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (PHINode).\n";
8505 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8507 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry "
8538 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8540 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (InsertElementInst).\n";
8554 TreeEntry *TE = nullptr;
8557 case TreeEntry::Vectorize:
8561 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (LoadInst).\n";
8565 << "SLP: added a new TreeEntry (jumbled LoadInst).\n";
8568 case TreeEntry::StridedVectorize:
8570 TE = newTreeEntry(VL, TreeEntry::StridedVectorize, Bundle, S,
8572 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (strided LoadInst).\n";
8575 case TreeEntry::ScatterVectorize:
8577 TE = newTreeEntry(VL, TreeEntry::ScatterVectorize, Bundle, S,
8581 << "SLP: added a new TreeEntry (non-consecutive LoadInst).\n";
8584 case TreeEntry::CombinedVectorize:
8585 case TreeEntry::NeedToGather:
8589 if (State == TreeEntry::ScatterVectorize)
8624 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8626 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (CastInst).\n";
8652 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8654 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (CmpInst).\n";
8723 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8726 dbgs() << "SLP: added a new TreeEntry "
8736 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8738 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (GetElementPtrInst).\n";
8795 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8798 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (StoreInst).\n";
8802 dbgs() << "SLP: added a new TreeEntry (jumbled StoreInst).\n";
8814 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8816 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (CallInst).\n";
8829 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
8832 LLVM_DEBUG(dbgs() << "SLP: added a new TreeEntry (isAltShuffle).\n";
8837 dbgs() << "SLP: added a new TreeEntry (ShuffleVectorInst).\n";
9048 void BoUpSLP::TreeEntry::buildAltOpShuffleMask(
9583 void BoUpSLP::reorderGatherNode(TreeEntry &TE) {
9795 TreeEntry &E = *VectorizableTree[Idx];
9802 TreeEntry &E = *VectorizableTree[Idx];
9914 if (TreeEntry *SE = getSameValuesTreeEntry(Slice.front(), Slice,
9953 if (E.State != TreeEntry::Vectorize)
9976 E.State = TreeEntry::StridedVectorize;
10003 E.State = TreeEntry::StridedVectorize;
10030 if (E.State != TreeEntry::Vectorize)
10036 E.CombinedOp = TreeEntry::MinMax;
10037 TreeEntry *CondEntry = const_cast<TreeEntry *>(getOperandEntry(&E, 0));
10039 CondEntry->State == TreeEntry::Vectorize) {
10041 CondEntry->State = TreeEntry::CombinedVectorize;
10067 [](const std::unique_ptr<TreeEntry> &TE) {
10081 for (std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
10082 TreeEntry &E = *TE;
10121 SmallVector<PointerUnion<Value *, const TreeEntry *>, 2> InVectors;
10323 void estimateNodesPermuteCost(const TreeEntry &E1, const TreeEntry *E2,
10333 cast<const TreeEntry *>(InVectors.front()) == &E1 &&
10334 cast<const TreeEntry *>(InVectors.back()) == E2) ||
10335 (!E2 && cast<const TreeEntry *>(InVectors.front()) == &E1)) {
10361 const auto *E = cast<const TreeEntry *>(InVectors.front());
10377 const auto *E = cast<const TreeEntry *>(P);
10433 createShuffle(const PointerUnion<Value *, const TreeEntry *> &P1,
10434 const PointerUnion<Value *, const TreeEntry *> &P2,
10441 auto GetNodeMinBWAffectedCost = [&](const TreeEntry &E,
10483 const TreeEntry *E = cast<const TreeEntry *>(P1);
10485 const TreeEntry *E2 = cast<const TreeEntry *>(P2);
10517 const TreeEntry *E = cast<const TreeEntry *>(P1);
10566 const TreeEntry *E2 = cast<const TreeEntry *>(P2);
10592 const TreeEntry *E1 = cast<const TreeEntry *>(P1);
10653 Value *adjustExtracts(const TreeEntry *E, MutableArrayRef<int> Mask,
10670 [&](const std::unique_ptr<TreeEntry> &TE) {
10701 ArrayRef<TreeEntry *> VEs = R.getTreeEntries(V);
10759 needToDelay(const TreeEntry *,
10760 ArrayRef<SmallVector<const TreeEntry *>>) const {
10764 void add(const TreeEntry &E1, const TreeEntry &E2, ArrayRef<int> Mask) {
10788 void add(const TreeEntry &E1, ArrayRef<int> Mask) {
10815 cast<const TreeEntry *>(InVectors.front())
10833 assert(InVectors.size() == 1 && isa<const TreeEntry *>(InVectors[0]) &&
10837 Value *Scalar = cast<const TreeEntry *>(InVectors[0])
10858 InVectors.front().dyn_cast<const TreeEntry *>()) {
10917 ArrayRef<std::pair<const TreeEntry *, unsigned>> SubVectors,
10922 const PointerUnion<Value *, const TreeEntry *> &Vec = InVectors.front();
10935 const PointerUnion<Value *, const TreeEntry *> &Vec = InVectors.front();
11017 const BoUpSLP::TreeEntry *BoUpSLP::getOperandEntry(const TreeEntry *E,
11019 if (const TreeEntry *VE = getMatchedVectorizedOperand(E, Idx))
11022 find_if(VectorizableTree, [&](const std::unique_ptr<TreeEntry> &TE) {
11032 TTI::CastContextHint BoUpSLP::getCastContextHint(const TreeEntry &TE) const {
11033 if (TE.State == TreeEntry::ScatterVectorize ||
11034 TE.State == TreeEntry::StridedVectorize)
11036 if (TE.State == TreeEntry::Vectorize && TE.getOpcode() == Instruction::Load &&
11073 BoUpSLP::getEntryCost(const TreeEntry *E, ArrayRef<Value *> VectorizedVals,
11108 if (!E->ReorderIndices.empty() && (E->State != TreeEntry::StridedVectorize ||
11125 assert((E->State == TreeEntry::Vectorize ||
11126 E->State == TreeEntry::ScatterVectorize ||
11127 E->State == TreeEntry::StridedVectorize) &&
11137 if (E->CombinedOp != TreeEntry::NotCombinedOp)
11149 if (ArrayRef<TreeEntry *> OpTEs = getTreeEntries(V); OpTEs.size() == 1)
11217 assert((E->State == TreeEntry::Vectorize ||
11218 E->State == TreeEntry::StridedVectorize) &&
11261 SmallPtrSet<const TreeEntry *, 4> CountedOps;
11272 if (const TreeEntry *OpTE =
11575 case TreeEntry::MinMax: {
11651 case TreeEntry::Vectorize:
11663 case TreeEntry::StridedVectorize: {
11671 case TreeEntry::ScatterVectorize: {
11679 case TreeEntry::CombinedVectorize:
11680 case TreeEntry::NeedToGather:
11689 if (E->State == TreeEntry::ScatterVectorize)
11712 if (E->State == TreeEntry::StridedVectorize) {
11719 assert(E->State == TreeEntry::Vectorize &&
11781 for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
11939 auto &&AreVectorizableGathers = [this](const TreeEntry *TE, unsigned Limit) {
11957 (VectorizableTree[0]->State == TreeEntry::Vectorize ||
11958 VectorizableTree[0]->State == TreeEntry::StridedVectorize ||
11973 if (VectorizableTree[0]->State == TreeEntry::Vectorize &&
11981 VectorizableTree[0]->State != TreeEntry::ScatterVectorize &&
11982 VectorizableTree[0]->State != TreeEntry::StridedVectorize))
12078 all_of(VectorizableTree, [&](const std::unique_ptr<TreeEntry> &TE) {
12106 if (any_of(VectorizableTree, [&](const std::unique_ptr<TreeEntry> &TE) {
12141 [](const std::unique_ptr<TreeEntry> &TE) {
12151 TreeEntry &E = *VectorizableTree[Idx];
12182 if (TEPtr->State != TreeEntry::Vectorize)
12452 TreeEntry &TE = *VectorizableTree[I];
12455 if (TE.State == TreeEntry::CombinedVectorize) {
12463 if (const TreeEntry *E =
12489 SmallVector<ShuffledInsertData<const TreeEntry *>> ShuffledInserts;
12492 DenseSet<std::pair<const TreeEntry *, Type *>> VectorCasts;
12494 DenseMap<const TreeEntry *, DenseSet<Value *>> ExtractsCount;
12537 const TreeEntry *ScalarTE = &EU.E;
12540 [this, VU](const ShuffledInsertData<const TreeEntry *> &Data) {
12604 const TreeEntry *Entry = &EU.E;
12752 if (ArrayRef<TreeEntry *> TEs = getTreeEntries(V); !TEs.empty()) {
12759 const TreeEntry &Root = *VectorizableTree.front();
12784 auto &&ResizeToVF = [this, &Cost](const TreeEntry *TE, ArrayRef<int> Mask,
12813 ArrayRef<const TreeEntry *> TEs) {
12856 (void)performExtractsShuffleAction<const TreeEntry>(
12858 [](const TreeEntry *E) { return E->getVectorFactor(); }, ResizeToVF,
12871 const TreeEntry &E = *VectorizableTree.front();
12904 const TreeEntry *OpTE = getOperandEntry(&E, 0);
13073 const TreeEntry *TE, ArrayRef<Value *> VL, MutableArrayRef<int> Mask,
13074 SmallVectorImpl<const TreeEntry *> &Entries, unsigned Part, bool ForOrder) {
13079 ? EdgeInfo(const_cast<TreeEntry *>(TE), 0)
13132 SmallVector<SmallPtrSet<const TreeEntry *, 4>> UsedTEs;
13138 SmallPtrSet<const TreeEntry *, 4> VToTEs;
13139 for (const TreeEntry *TEPtr : ValueToGatherNodes.find(V)->second) {
13174 if (ArrayRef<TreeEntry *> VTEs = getTreeEntries(V); !VTEs.empty()) {
13175 const TreeEntry *VTE = VTEs.front();
13177 VTEs.size() > 1 && VTE->State != TreeEntry::Vectorize) {
13180 const auto *MIt = find_if(VTEs, [](const TreeEntry *MTE) {
13181 return MTE->State == TreeEntry::Vectorize;
13205 SmallPtrSet<const TreeEntry *, 4> SavedVToTEs(VToTEs);
13207 for (SmallPtrSet<const TreeEntry *, 4> &Set : UsedTEs) {
13243 SmallVector<const TreeEntry *> FirstEntries(UsedTEs.front().begin(),
13245 sort(FirstEntries, [](const TreeEntry *TE1, const TreeEntry *TE2) {
13249 auto *It = find_if(FirstEntries, [=](const TreeEntry *EntryPtr) {
13279 DenseMap<int, const TreeEntry *> VFToTE;
13280 for (const TreeEntry *TE : UsedTEs.front()) {
13291 SmallVector<const TreeEntry *> SecondEntries(UsedTEs.back().begin(),
13293 sort(SecondEntries, [](const TreeEntry *TE1, const TreeEntry *TE2) {
13296 for (const TreeEntry *TE : SecondEntries) {
13309 UsedTEs.front(), [](const TreeEntry *TE1, const TreeEntry *TE2) {
13389 SmallVector<const TreeEntry *> TempEntries;
13478 ArrayRef<const TreeEntry *> Entries,
13545 const TreeEntry *BestEntry = nullptr;
13586 const TreeEntry *TE, ArrayRef<Value *> VL, SmallVectorImpl<int> &Mask,
13587 SmallVectorImpl<SmallVector<const TreeEntry *>> &Entries, unsigned NumParts,
13596 [](const std::unique_ptr<TreeEntry> &TE) {
13625 SmallVectorImpl<const TreeEntry *> &SubEntries = Entries.emplace_back();
13636 SmallVector<const TreeEntry *> LocalSubEntries;
13726 Instruction &BoUpSLP::getLastInstructionInBundle(const TreeEntry *E) {
13895 void BoUpSLP::setInsertPointAfterBundle(const TreeEntry *E) {
13978 if (ArrayRef<TreeEntry *> Entries = getTreeEntries(V); !Entries.empty()) {
14027 none_of(VectorizableTree, [&](const std::unique_ptr<TreeEntry> &TE) {
14206 Value *adjustExtracts(const TreeEntry *E, MutableArrayRef<int> Mask,
14224 if (ArrayRef<TreeEntry *> TEs = R.getTreeEntries(VecBase); !TEs.empty())
14233 ArrayRef<TreeEntry *> UTEs = R.getTreeEntries(U);
14239 [&](const std::unique_ptr<TreeEntry> &TE) {
14281 if (ArrayRef<TreeEntry *> TEs = R.getTreeEntries(VecOp);
14293 if (ArrayRef<TreeEntry *> TEs = R.getTreeEntries(VecOp); !TEs.empty())
14345 needToDelay(const TreeEntry *E,
14346 ArrayRef<SmallVector<const TreeEntry *>> Deps) const {
14348 if (all_of(Deps, [](ArrayRef<const TreeEntry *> TEs) {
14350 TEs, [](const TreeEntry *TE) { return TE->VectorizedValue; });
14363 void add(const TreeEntry &E1, const TreeEntry &E2, ArrayRef<int> Mask) {
14384 void add(const TreeEntry &E1, ArrayRef<int> Mask) {
14503 ArrayRef<std::pair<const TreeEntry *, unsigned>> SubVectors,
14607 BoUpSLP::TreeEntry *BoUpSLP::getMatchedVectorizedOperand(const TreeEntry *E,
14619 auto CheckSameVE = [&](const TreeEntry *VE) {
14625 [E, NodeIdx, VE](const std::unique_ptr<TreeEntry> &TE) {
14627 {const_cast<TreeEntry *>(E), NodeIdx}) &&
14631 TreeEntry *VE = getSameValuesTreeEntry(S.getMainOp(), VL);
14637 Value *BoUpSLP::vectorizeOperand(TreeEntry *E, unsigned NodeIdx,
14641 if (TreeEntry *VE = getMatchedVectorizedOperand(E, NodeIdx)) {
14653 SmallVector<std::pair<const TreeEntry *, unsigned>> SubVectors(
14710 find_if(VectorizableTree, [&](const std::unique_ptr<TreeEntry> &TE) {
14724 [E, NodeIdx](const std::unique_ptr<TreeEntry> &TE) {
14735 ResTy BoUpSLP::processBuildVector(const TreeEntry *E, Type *ScalarTy,
14749 SmallVector<std::pair<const TreeEntry *, unsigned>> SubVectors(
14780 TreeEntry *UserTE = E->UserTreeIndices.back().UserTE;
14786 find_if(VectorizableTree, [=](const std::unique_ptr<TreeEntry> &TE) {
14837 SmallVector<SmallVector<const TreeEntry *>> Entries;
14847 SmallVector<const TreeEntry *> ExtractEntries;
14851 if (ArrayRef<TreeEntry *> TEs = getTreeEntries(
14912 const TreeEntry *FrontTE = Entries.front().front();
14934 any_of(Entries, [&](ArrayRef<const TreeEntry *> TEs) {
14935 return any_of(TEs, [&](const TreeEntry *TE) {
15061 if (ArrayRef<TreeEntry *> TEs = getTreeEntries(VecOp);
15225 Value *BoUpSLP::createBuildVector(const TreeEntry *E, Type *ScalarTy,
15243 Value *BoUpSLP::vectorizeTree(TreeEntry *E, bool PostponedPHIs) {
15247 (E->State != TreeEntry::Vectorize || E->getOpcode() != Instruction::PHI ||
15276 auto FinalShuffle = [&](Value *V, const TreeEntry *E) {
15279 E->State == TreeEntry::Vectorize) {
15284 } else if (E->State == TreeEntry::StridedVectorize && IsReverseOrder) {
15289 SmallVector<std::pair<const TreeEntry *, unsigned>> SubVectors(
15306 const TreeEntry *OpE = getOperandEntry(E, Idx);
15391 if (ArrayRef<TreeEntry *> TEs = getTreeEntries(V); !TEs.empty())
15857 if (E->State == TreeEntry::Vectorize) {
15859 } else if (E->State == TreeEntry::StridedVectorize) {
15901 assert(E->State == TreeEntry::ScatterVectorize && "Unhandled state");
15952 if (E->State == TreeEntry::Vectorize) {
15955 assert(E->State == TreeEntry::StridedVectorize &&
16157 getOperandEntry(E, 0)->State == TreeEntry::NeedToGather ||
16158 getOperandEntry(E, 1)->State == TreeEntry::NeedToGather ||
16299 for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree) {
16311 for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree)
16312 if (TE->State == TreeEntry::Vectorize &&
16318 ArrayRef<const TreeEntry *> PostponedNodes = PostponedGathers.getArrayRef();
16319 DenseMap<Value *, SmallVector<TreeEntry *>> PostponedValues;
16320 for (const TreeEntry *E : PostponedNodes) {
16321 auto *TE = const_cast<TreeEntry *>(E);
16371 for (const TreeEntry *MNTE : getTreeEntries(V)) {
16382 for (const TreeEntry *BVE : ValueToGatherNodes.lookup(V)) {
16418 for (TreeEntry *VTE : It->getSecond())
16447 const TreeEntry *E = &ExternalUse.E;
16505 if (ArrayRef<TreeEntry *> ETEs = getTreeEntries(V); !ETEs.empty())
16568 ArrayRef<TreeEntry *> UseEntries = getTreeEntries(U);
16570 (E->State == TreeEntry::Vectorize ||
16571 E->State == TreeEntry::StridedVectorize) &&
16572 any_of(UseEntries, [&, TTI = TTI](TreeEntry *UseEntry) {
16573 return (UseEntry->State == TreeEntry::Vectorize ||
16575 TreeEntry::StridedVectorize) &&
16819 TreeEntry *Entry = TEPtr.get();
16868 const TreeEntry *IE = getTreeEntries(I).front();
16912 const TreeEntry &RootTE = *VectorizableTree.front();
17583 [[maybe_unused]] ArrayRef<TreeEntry *> SDTEs = getTreeEntries(SD->Inst);
17719 const TreeEntry &E, bool IsProfitableToDemoteRoot, unsigned &BitWidth,
17720 SmallVectorImpl<unsigned> &ToDemote, DenseSet<const TreeEntry *> &Visited,
17828 auto ProcessOperands = [&](ArrayRef<const TreeEntry *> Operands,
17832 for (const TreeEntry *Op : Operands) {
17872 [&](unsigned &BitWidth, ArrayRef<const TreeEntry *> Operands = {},
18009 SmallVector<const TreeEntry *> Ops(NumOps);
18024 SmallVector<const TreeEntry *, 2> Operands(1, getOperandEntry(&E, 0));
18142 VectorizableTree[NodeIdx]->State == TreeEntry::Vectorize &&
18157 [&](const TreeEntry &E, bool IsTopRoot, bool IsProfitableToDemoteRoot,
18169 ArrayRef<TreeEntry *> TEs = getTreeEntries(U);
18170 const TreeEntry *UserTE = E.UserTreeIndices.back().UserTE;
18180 if (all_of(TEs, [&](const TreeEntry *TE) {
18190 const TreeEntry *UserTE = E.UserTreeIndices.back().UserTE;
18290 DenseSet<const TreeEntry *> Visited;
18324 VectorizableTree.front()->State == TreeEntry::Vectorize &&
18354 VectorizableTree[NodeIdx]->State == TreeEntry::Vectorize &&
18446 TreeEntry *TE = VectorizableTree[Idx].get();