llvmorg-github-actions[bot] wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-llvm-ir @llvm/pr-subscribers-llvm-adt Author: Fangrui Song (MaskRay) <details> <summary>Changes</summary> Move getHeader, isReducible, getParentCycle, getDepth, and getNumBlocks off GenericCycle onto GenericCycleInfo, each taking the cycle by reference, so callers query a cycle through GenericCycleInfo instead of calling methods on it. This is a step toward replacing the GenericCycle pointer with an opaque handle. Aided by Claude Opus 4.8 --- Patch is 22.25 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/209990.diff 9 Files Affected: - (modified) llvm/include/llvm/ADT/GenericCycleImpl.h (+21-21) - (modified) llvm/include/llvm/ADT/GenericCycleInfo.h (+7-12) - (modified) llvm/include/llvm/ADT/GenericUniformityImpl.h (+35-34) - (modified) llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h (+2-2) - (modified) llvm/lib/CodeGen/MachineSink.cpp (+6-5) - (modified) llvm/lib/Target/AMDGPU/SIInstrInfo.cpp (+1-1) - (modified) llvm/lib/Target/AMDGPU/SILowerSGPRSpills.cpp (+2-2) - (modified) llvm/lib/Transforms/IPO/AttributorAttributes.cpp (+1-1) - (modified) llvm/lib/Transforms/Utils/FixIrreducible.cpp (+5-5) ``````````diff diff --git a/llvm/include/llvm/ADT/GenericCycleImpl.h b/llvm/include/llvm/ADT/GenericCycleImpl.h index 043b7f48501b8..c561a15084abb 100644 --- a/llvm/include/llvm/ADT/GenericCycleImpl.h +++ b/llvm/include/llvm/ADT/GenericCycleImpl.h @@ -84,7 +84,7 @@ auto GenericCycleInfo<ContextT>::getCyclePreheader(const CycleT &C) const if (!Predecessor) return nullptr; - assert(C.isReducible() && "Cycle Predecessor must be in a reducible cycle!"); + assert(isReducible(C) && "Cycle Predecessor must be in a reducible cycle!"); if (succ_size(Predecessor) != 1) return nullptr; @@ -99,13 +99,13 @@ auto GenericCycleInfo<ContextT>::getCyclePreheader(const CycleT &C) const template <typename ContextT> auto GenericCycleInfo<ContextT>::getCyclePredecessor(const CycleT &C) const -> BlockT * { - if (!C.isReducible()) + if (!isReducible(C)) return nullptr; BlockT *Out = nullptr; // Loop over the predecessors of the header node... - BlockT *Header = C.getHeader(); + BlockT *Header = getHeader(C); for (const auto Pred : predecessors(Header)) { if (!contains(C, Pred)) { if (Out && Out != Pred) @@ -120,7 +120,7 @@ auto GenericCycleInfo<ContextT>::getCyclePredecessor(const CycleT &C) const template <typename ContextT> void GenericCycleInfo<ContextT>::verifyCycle(const CycleT &C) const { #ifndef NDEBUG - assert(C.getNumBlocks() != 0 && "Cycle cannot be empty."); + assert(getNumBlocks(C) != 0 && "Cycle cannot be empty."); DenseSet<BlockT *> Blocks; for (BlockT *BB : getBlocks(C)) { assert(Blocks.insert(BB).second); // duplicates in block list? @@ -143,7 +143,7 @@ void GenericCycleInfo<ContextT>::verifyCycle(const CycleT &C) const { SmallPtrSet<BlockT *, 8> VisitedBBs; // Check the individual blocks. - for (BlockT *BB : depth_first_ext(C.getHeader(), VisitSet)) { + for (BlockT *BB : depth_first_ext(getHeader(C), VisitSet)) { assert(llvm::any_of(llvm::children<BlockT *>(BB), [&](BlockT *B) { return contains(C, B); }) && "Cycle block has no in-cycle successors!"); @@ -168,13 +168,13 @@ void GenericCycleInfo<ContextT>::verifyCycle(const CycleT &C) const { assert(!OutsideCyclePreds.contains(CB) && "Non-entry block reachable from outside!"); } - assert(BB != &C.getHeader()->getParent()->front() && + assert(BB != &getHeader(C)->getParent()->front() && "Cycle contains function entry block!"); VisitedBBs.insert(BB); } - if (VisitedBBs.size() != C.getNumBlocks()) { + if (VisitedBBs.size() != getNumBlocks(C)) { dbgs() << "The following blocks are unreachable in the cycle:\n "; ListSeparator LS; for (auto *BB : Blocks) { @@ -316,7 +316,7 @@ void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) { addToBlockMap(Block, Cycle); // Cycle and its ancestors gain the new block: extend each one's slice and // invalidate its exit-block cache in a single walk up the tree. - for (CycleT *C = Cycle; C; C = C->getParentCycle()) { + for (CycleT *C = Cycle; C; C = getParentCycle(*C)) { ++C->IdxEnd; if (!ExitBlocksCaches.empty()) ExitBlocksCaches[getCycleIndex(*C)].clear(); @@ -462,18 +462,18 @@ void GenericCycleInfoCompute<ContextT>::run(FunctionT *F) { LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": "); if (BlockParent != NewCycle) { - LLVM_DEBUG(errs() - << "discovered child cycle " - << Info.Context.print(BlockParent->getHeader()) << "\n"); + LLVM_DEBUG(errs() << "discovered child cycle " + << Info.Context.print(Info.getHeader(*BlockParent)) + << "\n"); // Make BlockParent the child of NewCycle. moveTopLevelCycleToNewParent(NewCycle, BlockParent); for (auto *ChildEntry : BlockParent->entries()) ProcessPredecessors(ChildEntry); } else { - LLVM_DEBUG(errs() - << "known child cycle " - << Info.Context.print(BlockParent->getHeader()) << "\n"); + LLVM_DEBUG(errs() << "known child cycle " + << Info.Context.print(Info.getHeader(*BlockParent)) + << "\n"); } } else { Info.addToBlockMap(Block, NewCycle); @@ -601,17 +601,17 @@ auto GenericCycleInfo<ContextT>::getSmallestCommonCycle(CycleT *A, // If cycles A and B have different depth replace them with parent cycle // until they have the same depth. - while (A->getDepth() > B->getDepth()) - A = A->getParentCycle(); - while (B->getDepth() > A->getDepth()) - B = B->getParentCycle(); + while (getDepth(*A) > getDepth(*B)) + A = getParentCycle(*A); + while (getDepth(*B) > getDepth(*A)) + B = getParentCycle(*B); // Cycles A and B are at same depth but may be disjoint, replace them with // parent cycles until we find cycle that contains both or we run out of // parent cycles. while (A != B) { - A = A->getParentCycle(); - B = B->getParentCycle(); + A = getParentCycle(*A); + B = getParentCycle(*B); } return A; @@ -638,7 +638,7 @@ void GenericCycleInfo<ContextT>::verifyCycleNest(bool VerifyFull) const { DenseSet<BlockT *> CycleHeaders; for (const CycleT &Cycle : cycles()) { - BlockT *Header = Cycle.getHeader(); + BlockT *Header = getHeader(Cycle); assert(CycleHeaders.insert(Header).second); if (VerifyFull) verifyCycle(Cycle); diff --git a/llvm/include/llvm/ADT/GenericCycleInfo.h b/llvm/include/llvm/ADT/GenericCycleInfo.h index 07995faffefc5..5219827cd4b9d 100644 --- a/llvm/include/llvm/ADT/GenericCycleInfo.h +++ b/llvm/include/llvm/ADT/GenericCycleInfo.h @@ -92,11 +92,6 @@ template <typename ContextT> class GenericCycle { public: GenericCycle() = default; - /// \brief Whether the cycle is a natural loop. - bool isReducible() const { return Entries.size() == 1; } - - BlockT *getHeader() const { return Entries[0]; } - const SmallVectorImpl<BlockT *> & getEntries() const { return Entries; } @@ -119,12 +114,6 @@ template <typename ContextT> class GenericCycle { return C && IdxBegin <= C->IdxBegin && C->IdxEnd <= IdxEnd; } - const GenericCycle *getParentCycle() const { return ParentCycle; } - GenericCycle *getParentCycle() { return ParentCycle; } - unsigned getDepth() const { return Depth; } - - size_t getNumBlocks() const { return IdxEnd - IdxBegin; } - /// Iteration over child cycles: the first child (if any) immediately /// follows this cycle in the preorder array, and each next sibling follows /// the previous child's subtree. @@ -249,6 +238,12 @@ template <typename ContextT> class GenericCycleInfo { return Number < BlockMap.size() ? BlockMap[Number] : nullptr; } + BlockT *getHeader(const CycleT &C) const { return C.Entries[0]; } + bool isReducible(const CycleT &C) const { return C.Entries.size() == 1; } + CycleT *getParentCycle(const CycleT &C) const { return C.ParentCycle; } + unsigned getDepth(const CycleT &C) const { return C.Depth; } + size_t getNumBlocks(const CycleT &C) const { return C.IdxEnd - C.IdxBegin; } + /// \brief Return whether \p Block is contained in \p C. O(1). bool contains(const CycleT &C, const BlockT *Block) const { return C.contains(getCycle(Block)); @@ -267,7 +262,7 @@ template <typename ContextT> class GenericCycleInfo { /// if it is not contained in any cycle. unsigned getCycleDepth(const BlockT *Block) const { CycleT *Cycle = getCycle(Block); - return Cycle ? Cycle->getDepth() : 0; + return Cycle ? getDepth(*Cycle) : 0; } CycleT *getTopLevelParentCycle(const BlockT *Block) const { diff --git a/llvm/include/llvm/ADT/GenericUniformityImpl.h b/llvm/include/llvm/ADT/GenericUniformityImpl.h index 630476daf2cd6..80a5e7236e5b8 100644 --- a/llvm/include/llvm/ADT/GenericUniformityImpl.h +++ b/llvm/include/llvm/ADT/GenericUniformityImpl.h @@ -641,18 +641,19 @@ template <typename ContextT> class DivergencePropagator { // Locate the largest ancestor cycle that is not reducible and does not // contain a reducible ancestor. This is done with a lambda that is defined // and invoked in the same statement. - const CycleT *IrreducibleAncestor = [](const CycleT *C) -> const CycleT * { + const CycleT *IrreducibleAncestor = + [this](const CycleT *C) -> const CycleT * { if (!C) return nullptr; - if (C->isReducible()) + if (CI.isReducible(*C)) return nullptr; - while (const CycleT *P = C->getParentCycle()) { - if (P->isReducible()) + while (const CycleT *P = CI.getParentCycle(*C)) { + if (CI.isReducible(*P)) return C; C = P; } - assert(!C->getParentCycle()); - assert(!C->isReducible()); + assert(!CI.getParentCycle(*C)); + assert(!CI.isReducible(*C)); return C; }(DivTermCycle); @@ -740,15 +741,15 @@ template <typename ContextT> class DivergencePropagator { // A cycle has exit divergence if the label of an exit block does // not match the label of its header. for (const auto *Cycle = CI.getCycle(&DivTermBlock); Cycle; - Cycle = Cycle->getParentCycle()) { - if (Cycle->isReducible()) { + Cycle = CI.getParentCycle(*Cycle)) { + if (CI.isReducible(*Cycle)) { // The exit divergence of a reducible cycle is recorded while // propagating labels. continue; } SmallVector<BlockT *> Exits; CI.getExitBlocks(*Cycle, Exits); - auto *Header = Cycle->getHeader(); + auto *Header = CI.getHeader(*Cycle); auto *HeaderLabel = BlockLabels[Header]; for (const auto *Exit : Exits) { if (BlockLabels[Exit] != HeaderLabel) { @@ -906,17 +907,17 @@ void GenericUniformityAnalysisImpl<ContextT>::propagateCycleExitDivergence( auto *OuterDivCycle = DivCycle; auto *ExitLevelCycle = CI.getCycle(&DivExit); const unsigned CycleExitDepth = - ExitLevelCycle ? ExitLevelCycle->getDepth() : 0; + ExitLevelCycle ? CI.getDepth(*ExitLevelCycle) : 0; // Find outer-most cycle that does not contain \p DivExit - while (DivCycle && DivCycle->getDepth() > CycleExitDepth) { + while (DivCycle && CI.getDepth(*DivCycle) > CycleExitDepth) { LLVM_DEBUG(dbgs() << " Found exiting cycle: " - << Context.print(DivCycle->getHeader()) << "\n"); + << Context.print(CI.getHeader(*DivCycle)) << "\n"); OuterDivCycle = DivCycle; - DivCycle = DivCycle->getParentCycle(); + DivCycle = CI.getParentCycle(*DivCycle); } LLVM_DEBUG(dbgs() << "\tOuter-most exiting cycle: " - << Context.print(OuterDivCycle->getHeader()) << "\n"); + << Context.print(CI.getHeader(*OuterDivCycle)) << "\n"); if (!DivergentExitCycles.insert(OuterDivCycle).second) return; @@ -994,20 +995,20 @@ const CycleT *getExtDivCycle(const CycleInfoT &CI, const CycleT *Cycle, return nullptr; const auto *OriginalCycle = Cycle; - const auto *Parent = Cycle->getParentCycle(); + const auto *Parent = CI.getParentCycle(*Cycle); while (Parent && !CI.contains(*Parent, DivTermBlock)) { Cycle = Parent; - Parent = Cycle->getParentCycle(); + Parent = CI.getParentCycle(*Cycle); } // If the original cycle is not the outermost cycle, then the outermost cycle // is irreducible. If the outermost cycle were reducible, then external // diverged paths would not reach the original inner cycle. (void)OriginalCycle; - assert(Cycle == OriginalCycle || !Cycle->isReducible()); + assert(Cycle == OriginalCycle || !CI.isReducible(*Cycle)); - if (Cycle->isReducible()) { - assert(Cycle->getHeader() == JoinBlock); + if (CI.isReducible(*Cycle)) { + assert(CI.getHeader(*Cycle) == JoinBlock); return nullptr; } @@ -1034,23 +1035,23 @@ const CycleT *getIntDivCycle(const CycleInfoT &CI, const CycleT *Cycle, // Find the smallest common cycle, if one exists. assert(Cycle && CI.contains(*Cycle, JoinBlock)); while (Cycle && !CI.contains(*Cycle, DivTermBlock)) { - Cycle = Cycle->getParentCycle(); + Cycle = CI.getParentCycle(*Cycle); } - if (!Cycle || Cycle->isReducible()) + if (!Cycle || CI.isReducible(*Cycle)) return nullptr; - if (DT.properlyDominates(Cycle->getHeader(), JoinBlock)) + if (DT.properlyDominates(CI.getHeader(*Cycle), JoinBlock)) return nullptr; - LLVM_DEBUG(dbgs() << " header " << Context.print(Cycle->getHeader()) + LLVM_DEBUG(dbgs() << " header " << Context.print(CI.getHeader(*Cycle)) << " does not dominate join\n"); - const auto *Parent = Cycle->getParentCycle(); - while (Parent && !DT.properlyDominates(Parent->getHeader(), JoinBlock)) { - LLVM_DEBUG(dbgs() << " header " << Context.print(Parent->getHeader()) + const auto *Parent = CI.getParentCycle(*Cycle); + while (Parent && !DT.properlyDominates(CI.getHeader(*Parent), JoinBlock)) { + LLVM_DEBUG(dbgs() << " header " << Context.print(CI.getHeader(*Parent)) << " does not dominate join\n"); Cycle = Parent; - Parent = Parent->getParentCycle(); + Parent = CI.getParentCycle(*Parent); } LLVM_DEBUG(dbgs() << " cycle made divergent by internal branch\n"); @@ -1085,7 +1086,7 @@ bool GenericUniformityAnalysisImpl<ContextT>::isTemporalDivergent( const BlockT *DefBlock = Def.getParent(); for (const CycleT *Cycle = CI.getCycle(DefBlock); Cycle && !CI.contains(*Cycle, &ObservingBlock); - Cycle = Cycle->getParentCycle()) { + Cycle = CI.getParentCycle(*Cycle)) { if (DivergentExitCycles.contains(Cycle)) { return true; } @@ -1124,8 +1125,8 @@ void GenericUniformityAnalysisImpl<ContextT>::analyzeControlDivergence( // Sort by order of decreasing depth. This allows later cycles to be skipped // because they are already contained in earlier ones. - llvm::sort(DivCycles, [](const CycleT *A, const CycleT *B) { - return A->getDepth() > B->getDepth(); + llvm::sort(DivCycles, [this](const CycleT *A, const CycleT *B) { + return CI.getDepth(*A) > CI.getDepth(*B); }); // Cycles that are assumed divergent due to the diverged entry @@ -1345,8 +1346,8 @@ void llvm::ModifiedPostOrder<ContextT>::computeStackPO( auto *NestedCycle = CI.getCycle(NextBB); if (Cycle != NestedCycle && (!Cycle || Cycle->contains(NestedCycle))) { LLVM_DEBUG(dbgs() << " found a cycle\n"); - while (NestedCycle->getParentCycle() != Cycle) - NestedCycle = NestedCycle->getParentCycle(); + while (CI.getParentCycle(*NestedCycle) != Cycle) + NestedCycle = CI.getParentCycle(*NestedCycle); SmallVector<BlockT *, 3> NestedExits; CI.getExitBlocks(*NestedCycle, NestedExits); @@ -1404,7 +1405,7 @@ void ModifiedPostOrder<ContextT>::computeCyclePO( SmallPtrSetImpl<const BlockT *> &Finalized) { LLVM_DEBUG(dbgs() << "inside computeCyclePO\n"); SmallVector<const BlockT *> Stack; - auto *CycleHeader = Cycle->getHeader(); + auto *CycleHeader = CI.getHeader(*Cycle); LLVM_DEBUG(dbgs() << " noted header: " << CI.getSSAContext().print(CycleHeader) << "\n"); @@ -1414,7 +1415,7 @@ void ModifiedPostOrder<ContextT>::computeCyclePO( // Visit the header last LLVM_DEBUG(dbgs() << " finishing header: " << CI.getSSAContext().print(CycleHeader) << "\n"); - appendBlock(*CycleHeader, Cycle->isReducible()); + appendBlock(*CycleHeader, CI.isReducible(*Cycle)); // Initialize with immediate successors for (auto *BB : successors(CycleHeader)) { diff --git a/llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h b/llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h index 1dbbee5c2dd72..19b03a0e581ff 100644 --- a/llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h +++ b/llvm/include/llvm/IR/GenericConvergenceVerifierImpl.h @@ -170,13 +170,13 @@ void GenericConvergenceVerifier<ContextT>::verify(const DominatorTreeT &DT) { {Context.print(User), CI.print(BBCycle)}); while (true) { - auto *Parent = BBCycle->getParentCycle(); + auto *Parent = CI.getParentCycle(*BBCycle); if (!Parent || CI.contains(*Parent, DefBB)) break; BBCycle = Parent; }; - Check(BBCycle->isReducible() && BB == BBCycle->getHeader(), + Check(CI.isReducible(*BBCycle) && BB == CI.getHeader(*BBCycle), "Cycle heart must dominate all blocks in the cycle.", {Context.print(User), Context.printAsOperand(BB), CI.print(BBCycle)}); Check(!CycleHearts.count(BBCycle), diff --git a/llvm/lib/CodeGen/MachineSink.cpp b/llvm/lib/CodeGen/MachineSink.cpp index 768abf7723013..0e2ce14876183 100644 --- a/llvm/lib/CodeGen/MachineSink.cpp +++ b/llvm/lib/CodeGen/MachineSink.cpp @@ -1121,7 +1121,7 @@ bool MachineSinking::isLegalToBreakCriticalEdge(MachineInstr &MI, // Check for backedges of more "complex" cycles. if (FromCycle == ToCycle && FromCycle && - (!FromCycle->isReducible() || FromCycle->getHeader() == ToBB)) + (!CI->isReducible(*FromCycle) || CI->getHeader(*FromCycle) == ToBB)) return false; // It's not always legal to break critical edges and sink the computation @@ -1345,8 +1345,9 @@ bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI, // impact for this operand. Defination outside of cycle means: // 1: defination is outside of cycle. // 2: defination is in this cycle, but it is a PHI in the cycle header. - if (Cycle != MCycle || (DefMI->isPHI() && Cycle && Cycle->isReducible() && - Cycle->getHeader() == DefMI->getParent())) + if (Cycle != MCycle || + (DefMI->isPHI() && Cycle && CI->isReducible(*Cycle) && + CI->getHeader(*Cycle) == DefMI->getParent())) continue; // The DefMI is defined inside the cycle. // If sinking this operand makes some register pressure set exceed limit, @@ -1913,8 +1914,8 @@ bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore, // Don't sink instructions into a cycle. if (!TryBreak && CI->getCycle(SuccToSinkTo) && - (!CI->getCycle(SuccToSinkTo)->isReducible() || - CI->getCycle(SuccToSinkTo)->getHeader() == SuccToSinkTo)) { + (!CI->isReducible(*CI->getCycle(SuccToSinkTo)) || + CI->getHeader(*CI->getCycle(SuccToSinkTo)) == SuccToSinkTo)) { LLVM_DEBUG(dbgs() << " *** NOTE: cycle header found\n"); TryBreak = true; } diff --git a/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp b/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp index 34cf595e8d39b..fd1946536df4f 100644 --- a/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp +++ b/llvm/lib/Target/AMDGPU/SIInstrInfo.cpp @@ -245,7 +245,7 @@ bool SIInstrInfo::isSafeToSink(MachineInstr &MI, return false; } - FromCycle = FromCycle->getParentCycle(); + FromCycle = CI->getParentCycle(*FromCycle); } } } diff --git a/llvm/lib/Target/AMDGPU/SILowerSGPRSpills.cpp b/llvm/lib/Target/AMDGPU/SILowerSGPRSpills.cpp index 48a38b1ffd460..7aa4e803e1268 100644 --- a/llvm/lib/Target/AMDGPU/SILowerSGPRSpills.cpp +++ b/llvm/lib/Target/AMDGPU/SILowerSGPRSpills.cpp @@ -305,8 +305,8 @@ bool SILowerSGPRSpills::spillCalleeSavedRegs( MachineBasicBlock *SILowerSGPRSpills::getCycleDomBB(MachineCycle *C) { // If the insertion point lands on a cycle entry, move it to a block that // dominates all entries. - if (C->isReducible()) { - if (auto *IDom = MDT->getNode(C->getHeader())->getIDom()) + if (MCI->isReducible(*C)) { + if (auto *IDom = MDT->getNode(MCI->getHeader(*C))->getIDom()) return IDom->getBlock(); llvm_unreachable("Expected cycle to have an IDom."); return nullptr; diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp index 66a05a077b208..fb70ee86920ca 100644 --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -223,7 +223,7 @@ static bool mayBeInCycle(const CycleInfo *CI, const Instruction *I, return false; if (CPtr) *CPtr = C; - return !HeaderOnly || BB == C->getHeader(); + return !HeaderOnly || BB == CI->getHeader(*C); } /// Checks if a type could have... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/209990 _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
