Lines Matching refs:TreeEntry
840 struct TreeEntry;
934 Optional<OrdersType> findReusedOrderedScalars(const TreeEntry &TE);
937 Optional<OrdersType> findPartiallyOrderedLoads(const TreeEntry &TE);
944 Optional<OrdersType> getReorderingData(const TreeEntry &TE, bool TopToBottom);
1032 EdgeInfo(TreeEntry *UserTE, unsigned EdgeIdx) in EdgeInfo()
1035 TreeEntry *UserTE = nullptr;
2095 canReorderOperands(TreeEntry *UserTE,
2096 SmallVectorImpl<std::pair<unsigned, TreeEntry *>> &Edges,
2097 ArrayRef<TreeEntry *> ReorderableGathers,
2098 SmallVectorImpl<TreeEntry *> &GatherOps);
2102 TreeEntry *getVectorizedOperand(TreeEntry *UserTE, unsigned OpIdx) { in getVectorizedOperand()
2104 TreeEntry *TE = nullptr; in getVectorizedOperand()
2116 const TreeEntry *getVectorizedOperand(const TreeEntry *UserTE, in getVectorizedOperand()
2119 const_cast<TreeEntry *>(UserTE), OpIdx); in getVectorizedOperand()
2127 InstructionCost getEntryCost(const TreeEntry *E,
2143 Value *vectorizeTree(TreeEntry *E);
2166 isGatherShuffledEntry(const TreeEntry *TE, SmallVectorImpl<int> &Mask,
2167 SmallVectorImpl<const TreeEntry *> &Entries);
2176 void setInsertPointAfterBundle(const TreeEntry *E);
2198 collectUserStores(const BoUpSLP::TreeEntry *TE) const;
2214 findExternalStoreUsersReorderIndices(TreeEntry *TE) const;
2216 struct TreeEntry { struct in llvm::slpvectorizer::BoUpSLP
2217 using VecTreeTy = SmallVector<std::unique_ptr<TreeEntry>, 8>; argument
2218 TreeEntry(VecTreeTy &Container) : Container(Container) {} in TreeEntry() function
2251 bool hasEqualOperands(const TreeEntry &TE) const { in hasEqualOperands() argument
2497 void dumpTreeCosts(const TreeEntry *E, InstructionCost ReuseShuffleCost, in dumpTreeCosts()
2511 TreeEntry *newTreeEntry(ArrayRef<Value *> VL, Optional<ScheduleData *> Bundle, in newTreeEntry()
2516 TreeEntry::EntryState EntryState = in newTreeEntry()
2517 Bundle ? TreeEntry::Vectorize : TreeEntry::NeedToGather; in newTreeEntry()
2522 TreeEntry *newTreeEntry(ArrayRef<Value *> VL, in newTreeEntry()
2523 TreeEntry::EntryState EntryState, in newTreeEntry()
2529 assert(((!Bundle && EntryState == TreeEntry::NeedToGather) || in newTreeEntry()
2530 (Bundle && EntryState != TreeEntry::NeedToGather)) && in newTreeEntry()
2532 VectorizableTree.push_back(std::make_unique<TreeEntry>(VectorizableTree)); in newTreeEntry()
2533 TreeEntry *Last = VectorizableTree.back().get(); in newTreeEntry()
2554 if (Last->State != TreeEntry::NeedToGather) { in newTreeEntry()
2587 TreeEntry::VecTreeTy VectorizableTree;
2599 TreeEntry *getTreeEntry(Value *V) { return ScalarToTreeEntry.lookup(V); } in getTreeEntry()
2601 const TreeEntry *getTreeEntry(Value *V) const { in getTreeEntry()
2606 SmallDenseMap<Value*, TreeEntry *> ScalarToTreeEntry;
2817 TreeEntry *TE = nullptr;
2983 if (TreeEntry *TE = BundleMember->TE) { in schedule()
3254 using TreeEntry = BoUpSLP::TreeEntry; typedef
3257 using NodeRef = TreeEntry *;
3259 using ContainerTy = BoUpSLP::TreeEntry::VecTreeTy;
3315 using TreeEntry = BoUpSLP::TreeEntry; typedef
3319 std::string getNodeLabel(const TreeEntry *Entry, const BoUpSLP *R) { in getNodeLabel()
3335 static std::string getNodeAttributes(const TreeEntry *Entry, in getNodeAttributes()
3337 if (Entry->State == TreeEntry::NeedToGather) in getNodeAttributes()
3411 BoUpSLP::findReusedOrderedScalars(const BoUpSLP::TreeEntry &TE) { in findReusedOrderedScalars()
3412 assert(TE.State == TreeEntry::NeedToGather && "Expected gather node only."); in findReusedOrderedScalars()
3417 const TreeEntry *STE = nullptr; in findReusedOrderedScalars()
3640 BoUpSLP::findPartiallyOrderedLoads(const BoUpSLP::TreeEntry &TE) { in findPartiallyOrderedLoads()
3641 assert(TE.State == TreeEntry::NeedToGather && "Expected gather node only."); in findPartiallyOrderedLoads()
3659 Optional<BoUpSLP::OrdersType> BoUpSLP::getReorderingData(const TreeEntry &TE, in getReorderingData()
3665 if (TE.State == TreeEntry::Vectorize && in getReorderingData()
3670 if (TE.State == TreeEntry::NeedToGather) { in getReorderingData()
3708 DenseMap<unsigned, SetVector<TreeEntry *>> VFToOrderedEntries; in reorderTopToBottom()
3711 DenseMap<const TreeEntry *, OrdersType> GathersToOrders; in reorderTopToBottom()
3715 DenseMap<const TreeEntry *, OrdersType> AltShufflesToOrders; in reorderTopToBottom()
3718 DenseMap<const TreeEntry *, SmallVector<OrdersType, 1>> in reorderTopToBottom()
3728 const std::unique_ptr<TreeEntry> &TE) { in reorderTopToBottom()
3769 const TreeEntry *UserTE = TE.get(); in reorderTopToBottom()
3774 return EI.UserTE->State == TreeEntry::Vectorize && in reorderTopToBottom()
3782 if (TE->State != TreeEntry::Vectorize) in reorderTopToBottom()
3796 ArrayRef<TreeEntry *> OrderedEntries = It->second.getArrayRef(); in reorderTopToBottom()
3802 SmallPtrSet<const TreeEntry *, 4> VisitedOps; in reorderTopToBottom()
3803 for (const TreeEntry *OpTE : OrderedEntries) { in reorderTopToBottom()
3811 if (OpTE->State == TreeEntry::NeedToGather) { in reorderTopToBottom()
3834 if (OpTE->State == TreeEntry::Vectorize && !OpTE->isAltShuffle() && in reorderTopToBottom()
3872 for (std::unique_ptr<TreeEntry> &TE : VectorizableTree) { in reorderTopToBottom()
3892 if (TE->State == TreeEntry::Vectorize && in reorderTopToBottom()
3923 TreeEntry *UserTE, SmallVectorImpl<std::pair<unsigned, TreeEntry *>> &Edges, in canReorderOperands()
3924 ArrayRef<TreeEntry *> ReorderableGathers, in canReorderOperands()
3925 SmallVectorImpl<TreeEntry *> &GatherOps) { in canReorderOperands()
3927 if (any_of(Edges, [I](const std::pair<unsigned, TreeEntry *> &OpData) { in canReorderOperands()
3929 OpData.second->State == TreeEntry::Vectorize; in canReorderOperands()
3932 if (TreeEntry *TE = getVectorizedOperand(UserTE, I)) { in canReorderOperands()
3945 if (TE->State != TreeEntry::Vectorize && TE->ReuseShuffleIndices.empty()) in canReorderOperands()
3949 TreeEntry *Gather = nullptr; in canReorderOperands()
3951 [&Gather, UserTE, I](TreeEntry *TE) { in canReorderOperands()
3952 assert(TE->State != TreeEntry::Vectorize && in canReorderOperands()
3974 SetVector<TreeEntry *> OrderedEntries; in reorderBottomToTop()
3975 DenseMap<const TreeEntry *, OrdersType> GathersToOrders; in reorderBottomToTop()
3979 SmallVector<TreeEntry *> NonVectorized; in reorderBottomToTop()
3982 const std::unique_ptr<TreeEntry> &TE) { in reorderBottomToTop()
3983 if (TE->State != TreeEntry::Vectorize) in reorderBottomToTop()
3988 if (TE->State != TreeEntry::Vectorize) in reorderBottomToTop()
3997 SmallPtrSet<const TreeEntry *, 4> Visited; in reorderBottomToTop()
4001 DenseMap<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>> Users; in reorderBottomToTop()
4002 SmallVector<TreeEntry *> Filtered; in reorderBottomToTop()
4003 for (TreeEntry *TE : OrderedEntries) { in reorderBottomToTop()
4004 if (!(TE->State == TreeEntry::Vectorize || in reorderBottomToTop()
4005 (TE->State == TreeEntry::NeedToGather && in reorderBottomToTop()
4019 TreeEntry *UserTE = EI.UserTE; in reorderBottomToTop()
4028 [&OrderedEntries](TreeEntry *TE) { OrderedEntries.remove(TE); }); in reorderBottomToTop()
4030 std::pair<TreeEntry *, SmallVector<std::pair<unsigned, TreeEntry *>>>> in reorderBottomToTop()
4037 SmallVector<TreeEntry *> GatherOps; in reorderBottomToTop()
4041 [&OrderedEntries](const std::pair<unsigned, TreeEntry *> &Op) { in reorderBottomToTop()
4054 SmallPtrSet<const TreeEntry *, 4> VisitedOps; in reorderBottomToTop()
4055 SmallPtrSet<const TreeEntry *, 4> VisitedUsers; in reorderBottomToTop()
4057 TreeEntry *OpTE = Op.second; in reorderBottomToTop()
4063 if (OpTE->State == TreeEntry::NeedToGather) in reorderBottomToTop()
4068 Data.second, [OpTE](const std::pair<unsigned, TreeEntry *> &P) { in reorderBottomToTop()
4072 if (OpTE->State == TreeEntry::Vectorize && !OpTE->isAltShuffle() && in reorderBottomToTop()
4089 const TreeEntry *TE) { in reorderBottomToTop()
4091 (TE->State == TreeEntry::Vectorize && TE->isAltShuffle()) || in reorderBottomToTop()
4094 if (TE->State == TreeEntry::NeedToGather) { in reorderBottomToTop()
4103 TreeEntry *UserTE = EI.UserTE; in reorderBottomToTop()
4116 ArrayRef<std::pair<unsigned, TreeEntry *>> Ops = Users[UserTE]; in reorderBottomToTop()
4119 const std::pair<unsigned, TreeEntry *> &Op) { in reorderBottomToTop()
4132 [&OrderedEntries](const std::pair<unsigned, TreeEntry *> &Op) { in reorderBottomToTop()
4149 [&OrderedEntries](const std::pair<unsigned, TreeEntry *> &Op) { in reorderBottomToTop()
4163 for (const std::pair<unsigned, TreeEntry *> &Op : Data.second) { in reorderBottomToTop()
4164 TreeEntry *TE = Op.second; in reorderBottomToTop()
4174 if (TE->State != TreeEntry::Vectorize) in reorderBottomToTop()
4184 for (TreeEntry *Gather : GatherOps) { in reorderBottomToTop()
4197 if (Data.first->State != TreeEntry::Vectorize || in reorderBottomToTop()
4228 TreeEntry *Entry = TEPtr.get(); in buildExternalUses()
4231 if (Entry->State == TreeEntry::NeedToGather) in buildExternalUses()
4257 if (TreeEntry *UseEntry = getTreeEntry(U)) { in buildExternalUses()
4263 UseEntry->State == TreeEntry::ScatterVectorize || in buildExternalUses()
4267 assert(UseEntry->State != TreeEntry::NeedToGather && "Bad state"); in buildExternalUses()
4285 BoUpSLP::collectUserStores(const BoUpSLP::TreeEntry *TE) const { in collectUserStores()
4398 BoUpSLP::findExternalStoreUsersReorderIndices(TreeEntry *TE) const { in findExternalStoreUsersReorderIndices()
4701 UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize; in buildTree_rec()
4746 if (TreeEntry *E = getTreeEntry(S.OpValue)) { in buildTree_rec()
4794 UserTreeIdx.UserTE->State == TreeEntry::ScatterVectorize) { in buildTree_rec()
4873 TreeEntry *TE = in buildTree_rec()
4981 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5005 TreeEntry *TE = nullptr; in buildTree_rec()
5025 TE = newTreeEntry(VL, TreeEntry::ScatterVectorize, Bundle, S, in buildTree_rec()
5075 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5109 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5157 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5239 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5345 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, in buildTree_rec()
5352 TreeEntry *TE = in buildTree_rec()
5437 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5465 TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx, in buildTree_rec()
5811 InstructionCost BoUpSLP::getEntryCost(const TreeEntry *E, in getEntryCost()
5849 const TreeEntry *VE = getTreeEntry(V); in getEntryCost()
5915 if (E->State == TreeEntry::NeedToGather) { in getEntryCost()
5921 SmallVector<const TreeEntry *> Entries; in getEntryCost()
6093 assert((E->State == TreeEntry::Vectorize || in getEntryCost()
6094 E->State == TreeEntry::ScatterVectorize) && in getEntryCost()
6459 if (E->State == TreeEntry::Vectorize) { in getEntryCost()
6463 assert(E->State == TreeEntry::ScatterVectorize && "Unknown EntryState"); in getEntryCost()
6542 for (const std::unique_ptr<TreeEntry> &TE : VectorizableTree) { in getEntryCost()
6612 auto &&AreVectorizableGathers = [this](const TreeEntry *TE, unsigned Limit) { in isFullyVectorizableTinyTree()
6614 return TE->State == TreeEntry::NeedToGather && in isFullyVectorizableTinyTree()
6625 (TE->State == TreeEntry::NeedToGather && in isFullyVectorizableTinyTree()
6631 (VectorizableTree[0]->State == TreeEntry::Vectorize || in isFullyVectorizableTinyTree()
6646 if (VectorizableTree[0]->State == TreeEntry::Vectorize && in isFullyVectorizableTinyTree()
6652 if (VectorizableTree[0]->State == TreeEntry::NeedToGather || in isFullyVectorizableTinyTree()
6653 (VectorizableTree[1]->State == TreeEntry::NeedToGather && in isFullyVectorizableTinyTree()
6654 VectorizableTree[0]->State != TreeEntry::ScatterVectorize)) in isFullyVectorizableTinyTree()
6727 VectorizableTree[1]->State == TreeEntry::NeedToGather && in isTreeTinyAndNotFullyVectorizable()
7043 TreeEntry &TE = *VectorizableTree[I]; in getTreeCost()
7055 SmallVector<MapVector<const TreeEntry *, SmallVector<int>>> ShuffleMasks; in getTreeCost()
7056 SmallVector<std::pair<Value *, const TreeEntry *>> FirstUsers; in getTreeCost()
7085 const TreeEntry *ScalarTE = getTreeEntry(EU.Scalar); in getTreeCost()
7088 [VU](const std::pair<Value *, const TreeEntry *> &Pair) { in getTreeCost()
7106 if (const TreeEntry *E = getTreeEntry(IEBase)) { in getTreeCost()
7159 auto &&ResizeToVF = [this, &Cost](const TreeEntry *TE, ArrayRef<int> Mask) { in getTreeCost()
7192 ArrayRef<const TreeEntry *> TEs) { in getTreeCost()
7220 (void)performExtractsShuffleAction<const TreeEntry>( in getTreeCost()
7222 [](const TreeEntry *E) { return E->getVectorFactor(); }, ResizeToVF, in getTreeCost()
7247 BoUpSLP::isGatherShuffledEntry(const TreeEntry *TE, SmallVectorImpl<int> &Mask, in isGatherShuffledEntry()
7248 SmallVectorImpl<const TreeEntry *> &Entries) { in isGatherShuffledEntry()
7254 DenseMap<Value *, SmallPtrSet<const TreeEntry *, 4>> ValueToTEs; in isGatherShuffledEntry()
7255 for (const std::unique_ptr<TreeEntry> &EntryPtr : VectorizableTree) { in isGatherShuffledEntry()
7258 if (EntryPtr->State != TreeEntry::NeedToGather) in isGatherShuffledEntry()
7270 SmallVector<SmallPtrSet<const TreeEntry *, 4>> UsedTEs; in isGatherShuffledEntry()
7276 SmallPtrSet<const TreeEntry *, 4> VToTEs; in isGatherShuffledEntry()
7280 if (const TreeEntry *VTE = getTreeEntry(V)) in isGatherShuffledEntry()
7291 SmallPtrSet<const TreeEntry *, 4> SavedVToTEs(VToTEs); in isGatherShuffledEntry()
7293 for (SmallPtrSet<const TreeEntry *, 4> &Set : UsedTEs) { in isGatherShuffledEntry()
7329 auto It = find_if(UsedTEs.front(), [TE](const TreeEntry *EntryPtr) { in isGatherShuffledEntry()
7342 DenseMap<int, const TreeEntry *> VFToTE; in isGatherShuffledEntry()
7343 for (const TreeEntry *TE : UsedTEs.front()) in isGatherShuffledEntry()
7345 for (const TreeEntry *TE : UsedTEs.back()) { in isGatherShuffledEntry()
7366 const TreeEntry *VTE = Entries[Idx]; in isGatherShuffledEntry()
7441 void BoUpSLP::setInsertPointAfterBundle(const TreeEntry *E) { in setInsertPointAfterBundle()
7504 if (E->State != TreeEntry::NeedToGather && in setInsertPointAfterBundle()
7600 if (TreeEntry *Entry = getTreeEntry(V)) { in gather()
7706 if (TreeEntry *E = getTreeEntry(S.OpValue)) in vectorizeTree()
7765 [VL](const std::unique_ptr<TreeEntry> &TE) { in createBuildVector()
7766 return TE->State == TreeEntry::NeedToGather && TE->isSame(VL); in createBuildVector()
7826 Value *BoUpSLP::vectorizeTree(TreeEntry *E) { in vectorizeTree()
7838 if (E->State == TreeEntry::NeedToGather) { in vectorizeTree()
7843 SmallVector<const TreeEntry *> Entries; in vectorizeTree()
7866 assert((E->State == TreeEntry::Vectorize || in vectorizeTree()
7867 E->State == TreeEntry::ScatterVectorize) && in vectorizeTree()
8165 if (E->State == TreeEntry::Vectorize) { in vectorizeTree()
8172 if (TreeEntry *Entry = getTreeEntry(PO)) { in vectorizeTree()
8179 assert(E->State == TreeEntry::ScatterVectorize && "Unhandled state"); in vectorizeTree()
8216 if (TreeEntry *Entry = getTreeEntry(ScalarPtr)) { in vectorizeTree()
8318 if (TreeEntry *Entry = getTreeEntry(ScalarArg)) { in vectorizeTree()
8481 TreeEntry *E = getTreeEntry(Scalar); in vectorizeTree()
8483 assert(E->State != TreeEntry::NeedToGather && in vectorizeTree()
8577 if (const TreeEntry *E = getTreeEntry(IEBase)) { in vectorizeTree()
8860 TreeEntry *Entry = TEPtr.get(); in vectorizeTree()
8863 if (Entry->State == TreeEntry::NeedToGather) in vectorizeTree()
9569 TreeEntry *SDTE = getTreeEntry(SD->Inst); in scheduleBlock()