llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-adt Author: Fangrui Song (MaskRay) <details> <summary>Changes</summary> Assign each cycle a preorder ID in layoutBlocks's Euler-tour walk and move the caches into a lazily allocated table indexed by ID, shrinking sizeof(GenericCycle) from 128 to 80. appendEntry/setSingleEntry no longer invalidate: the exit-block set does not depend on entries. Delete the unused GenericCycle::clear. Aided by Claude Fable 5 --- Full diff: https://github.com/llvm/llvm-project/pull/209666.diff 2 Files Affected: - (modified) llvm/include/llvm/ADT/GenericCycleImpl.h (+19-12) - (modified) llvm/include/llvm/ADT/GenericCycleInfo.h (+10-21) ``````````diff diff --git a/llvm/include/llvm/ADT/GenericCycleImpl.h b/llvm/include/llvm/ADT/GenericCycleImpl.h index 02e6770f0aedd..780ea9906150e 100644 --- a/llvm/include/llvm/ADT/GenericCycleImpl.h +++ b/llvm/include/llvm/ADT/GenericCycleImpl.h @@ -36,29 +36,31 @@ namespace llvm { template <typename ContextT> void GenericCycleInfo<ContextT>::getExitBlocks( const CycleT &C, SmallVectorImpl<BlockT *> &TmpStorage) const { - if (!C.ExitBlocksCache.empty()) { - TmpStorage.append(C.ExitBlocksCache.begin(), C.ExitBlocksCache.end()); + if (ExitBlocksCaches.empty()) + ExitBlocksCaches.resize(NumCycles); + auto &Cache = ExitBlocksCaches[C.ID]; + if (!Cache.empty()) { + TmpStorage.append(Cache.begin(), Cache.end()); return; } size_t NumExitBlocks = 0; for (BlockT *Block : getBlocks(C)) { - llvm::append_range(C.ExitBlocksCache, successors(Block)); + llvm::append_range(Cache, successors(Block)); - for (size_t Idx = NumExitBlocks, End = C.ExitBlocksCache.size(); Idx < End; - ++Idx) { - BlockT *Succ = C.ExitBlocksCache[Idx]; + for (size_t Idx = NumExitBlocks, End = Cache.size(); Idx < End; ++Idx) { + BlockT *Succ = Cache[Idx]; if (!contains(&C, Succ)) { - auto ExitEndIt = C.ExitBlocksCache.begin() + NumExitBlocks; - if (std::find(C.ExitBlocksCache.begin(), ExitEndIt, Succ) == ExitEndIt) - C.ExitBlocksCache[NumExitBlocks++] = Succ; + auto ExitEndIt = Cache.begin() + NumExitBlocks; + if (std::find(Cache.begin(), ExitEndIt, Succ) == ExitEndIt) + Cache[NumExitBlocks++] = Succ; } } - C.ExitBlocksCache.resize(NumExitBlocks); + Cache.resize(NumExitBlocks); } - TmpStorage.append(C.ExitBlocksCache.begin(), C.ExitBlocksCache.end()); + TmpStorage.append(Cache.begin(), Cache.end()); } template <typename ContextT> @@ -328,7 +330,8 @@ void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) { // invalidate its exit-block cache in a single walk up the tree. for (CycleT *C = Cycle; C; C = C->getParentCycle()) { ++C->IdxEnd; - C->clearCache(); + if (!ExitBlocksCaches.empty()) + ExitBlocksCaches[C->ID].clear(); } } @@ -348,7 +351,9 @@ void GenericCycleInfo<ContextT>::layoutBlocks(ArrayRef<BlockT *> Order) { }; SmallVector<Frame, 8> Stack; unsigned Cursor = 0; + NumCycles = 0; auto enter = [&](CycleT *C) { + C->ID = NumCycles++; Cursor += C->IdxEnd; // IdxEnd currently holds C's own-block count. C->IdxBegin = Cursor; Stack.push_back({C, C->child_begin(), C->child_end()}); @@ -558,6 +563,8 @@ template <typename ContextT> void GenericCycleInfo<ContextT>::clear() { TopLevelCycles.clear(); BlockMap.clear(); BlockLayout.clear(); + NumCycles = 0; + ExitBlocksCaches.clear(); } /// \brief Compute the cycle info for a function. diff --git a/llvm/include/llvm/ADT/GenericCycleInfo.h b/llvm/include/llvm/ADT/GenericCycleInfo.h index d3ffafc7d0d39..d4033b1f214f1 100644 --- a/llvm/include/llvm/ADT/GenericCycleInfo.h +++ b/llvm/include/llvm/ADT/GenericCycleInfo.h @@ -82,22 +82,11 @@ template <typename ContextT> class GenericCycle { /// always have the same depth. unsigned Depth = 0; - /// Cache for the results of GetExitBlocks - mutable SmallVector<BlockT *, 4> ExitBlocksCache; + /// Preorder number of this cycle in the forest, assigned by layoutBlocks. + /// Indexes per-cycle side tables in GenericCycleInfo. + unsigned ID = 0; - void clear() { - Entries.clear(); - Children.clear(); - IdxBegin = IdxEnd = 0; - Depth = 0; - ParentCycle = nullptr; - clearCache(); - } - - void appendEntry(BlockT *Block) { - Entries.push_back(Block); - clearCache(); - } + void appendEntry(BlockT *Block) { Entries.push_back(Block); } GenericCycle(const GenericCycle &) = delete; GenericCycle &operator=(const GenericCycle &) = delete; @@ -116,11 +105,6 @@ template <typename ContextT> class GenericCycle { return Entries; } - /// Clear the cache of the cycle. - /// This should be run in all non-const function in GenericCycle - /// and GenericCycleInfo. - void clearCache() const { ExitBlocksCache.clear(); } - /// \brief Return whether \p Block is an entry block of the cycle. bool isEntry(const BlockT *Block) const { return is_contained(Entries, Block); @@ -131,7 +115,6 @@ template <typename ContextT> class GenericCycle { void setSingleEntry(BlockT *Block) { Entries.clear(); Entries.push_back(Block); - clearCache(); } /// \brief Returns true iff this cycle contains \p C. O(1). Non-strict, i.e. @@ -219,6 +202,12 @@ template <typename ContextT> class GenericCycleInfo { /// slice [IdxBegin, IdxEnd) of this array, nested inside its parent's. SmallVector<BlockT *, 8> BlockLayout; + unsigned NumCycles = 0; + + /// getExitBlocks caches, indexed by CycleT::ID. Empty until the first + /// query, then sized to NumCycles. + mutable SmallVector<SmallVector<BlockT *, 0>, 0> ExitBlocksCaches; + /// Top-level cycles discovered by any DFS. /// /// Note: The implementation treats the nullptr as the parent of `````````` </details> https://github.com/llvm/llvm-project/pull/209666 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
