https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/203197
>From dd8c5c240de957b9e8e3da8febd6e7cb2048b04a Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Thu, 11 Jun 2026 06:02:24 +0000 Subject: [PATCH] [LoopInterchange] Consolidate induction and reduction vars check --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 165 ++++++++---------- .../reduction2mem-limitation.ll | 14 +- 2 files changed, 75 insertions(+), 104 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index f0cf9d6d4724f..543f527941b29 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -461,10 +461,6 @@ class LoopInterchangeLegality { bool canInterchangeLoops(unsigned InnerLoopId, unsigned OuterLoopId, CharMatrix &DepMatrix); - /// Discover induction PHIs in the header of \p L. Induction - /// PHIs are added to \p Inductions. - bool findInductions(Loop *L, SmallVectorImpl<PHINode *> &Inductions); - /// Check if the loop structure is understood. We do not handle triangular /// loops for now. bool isLoopStructureUnderstood(); @@ -511,13 +507,17 @@ class LoopInterchangeLegality { bool tightlyNested(Loop *Outer, Loop *Inner); bool containsUnsafeInstructions(BasicBlock *BB, Instruction *Skip); - /// Discover induction and reduction PHIs in the header of \p L. Induction - /// PHIs are added to \p Inductions, reductions are added to - /// OuterInnerReductions. When the outer loop is passed, the inner loop needs - /// to be passed as \p InnerLoop. - bool findInductionAndReductions(Loop *L, - SmallVector<PHINode *, 8> &Inductions, - Loop *InnerLoop); + /// Traverse all PHI nodes in the header of each loop in the loop nest + /// starting from \p OuterLoop, and perform the following checks: + /// + /// - Identify induction variables in the child loop of \p OuterLoop. + /// - Check for reductions across the inner loop and \p OuterLoop. + /// - Detect unsupported PHI nodes. + /// + /// Return false if any unsupported PHI node is found or if no induction + /// variable is found in the child loop of \p OuterLoop. Otherwise return + /// true. + bool checkInductionsAndReductions(Loop *OuterLoop); /// Detect and record the reduction of the inner loop. Add them to /// InnerReductions. @@ -1239,32 +1239,31 @@ bool LoopInterchangeLegality::isInnerReduction( return true; } -bool LoopInterchangeLegality::findInductionAndReductions( - Loop *L, SmallVector<PHINode *, 8> &Inductions, Loop *InnerLoop) { - if (!L->getLoopLatch() || !L->getLoopPredecessor()) - return false; - for (PHINode &PHI : L->getHeader()->phis()) { - InductionDescriptor ID; - if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID)) - Inductions.push_back(&PHI); - else { - // PHIs in inner loops need to be part of a reduction in the outer loop, - // discovered when checking the PHIs of the outer loop earlier. - if (!InnerLoop) { - if (OuterInnerReductions.count(&PHI)) { - LLVM_DEBUG(dbgs() << "Found a reduction across the outer loop.\n"); - } else if (EnableReduction2Memory && - isInnerReduction(L, &PHI, HasNoWrapReductions)) { - LLVM_DEBUG(dbgs() << "Found a reduction in the inner loop: \n" - << PHI << '\n'); - } else - return false; - } else { +bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) { + auto ChildLoop = [](Loop *L) { + assert(L->getSubLoops().size() <= 1 && + "Expect at most one child loop for now."); + return L->getSubLoops().empty() ? nullptr : L->getSubLoops().front(); + }; + + Loop *InnerLoop = ChildLoop(OuterLoop); + for (Loop *CurLoop = OuterLoop; CurLoop; CurLoop = ChildLoop(CurLoop)) { + for (PHINode &PHI : CurLoop->getHeader()->phis()) { + InductionDescriptor ID; + if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) { + if (CurLoop == InnerLoop) + InnerLoopInductions.push_back(&PHI); + continue; + } + + if (CurLoop == OuterLoop) { + // PHIs in inner loops need to be part of a reduction in the outer loop, assert(PHI.getNumIncomingValues() == 2 && "Phis in loop header should have exactly 2 incoming values"); // Check if we have a PHI node in the outer loop that has a reduction // result from the inner loop as an incoming value. - Value *V = followLCSSA(PHI.getIncomingValueForBlock(L->getLoopLatch())); + Value *V = followLCSSA( + PHI.getIncomingValueForBlock(OuterLoop->getLoopLatch())); PHINode *InnerRedPhi = findInnerReductionPhi( InnerLoop, V, HasNoWrapReductions, HasNoInfInsts); if (!InnerRedPhi || @@ -1272,26 +1271,51 @@ bool LoopInterchangeLegality::findInductionAndReductions( LLVM_DEBUG( dbgs() << "Failed to recognize PHI as an induction or reduction.\n"); + ORE->emit([&]() { + return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter", + OuterLoop->getStartLoc(), + OuterLoop->getHeader()) + << "Only outer loops with induction or reduction PHI nodes " + "can be interchanged currently."; + }); return false; } OuterInnerReductions.insert(&PHI); OuterInnerReductions.insert(InnerRedPhi); + } else { + if (OuterInnerReductions.count(&PHI)) { + LLVM_DEBUG(dbgs() << "Found a reduction across the outer loop.\n"); + } else if (EnableReduction2Memory && + isInnerReduction(CurLoop, &PHI, HasNoWrapReductions)) { + LLVM_DEBUG(dbgs() << "Found a reduction in the inner loop: \n" + << PHI << '\n'); + } else { + ORE->emit([&]() { + return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner", + CurLoop->getStartLoc(), + CurLoop->getHeader()) + << "Only inner loops with induction or reduction PHI nodes " + "can be interchanged currently."; + }); + return false; + } } } - } - // For now we only support at most one reduction. - if (InnerReductions.size() > 1) { - LLVM_DEBUG(dbgs() << "Only supports at most one reduction.\n"); - ORE->emit([&]() { - return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction", - L->getStartLoc(), L->getHeader()) - << "Only supports at most one reduction."; - }); - return false; + // For now we only support at most one reduction. + if (InnerReductions.size() > 1) { + LLVM_DEBUG(dbgs() << "Only supports at most one reduction.\n"); + ORE->emit([&]() { + return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedInnerReduction", + CurLoop->getStartLoc(), + CurLoop->getHeader()) + << "Only supports at most one reduction."; + }); + return false; + } } - return true; + return !InnerLoopInductions.empty(); } // This function indicates the current limitations in the transform as a result @@ -1318,44 +1342,6 @@ bool LoopInterchangeLegality::currentLimitations() { return true; } - SmallVector<PHINode *, 8> Inductions; - if (!findInductionAndReductions(OuterLoop, Inductions, InnerLoop)) { - LLVM_DEBUG( - dbgs() << "Only outer loops with induction or reduction PHI nodes " - << "are supported currently.\n"); - ORE->emit([&]() { - return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIOuter", - OuterLoop->getStartLoc(), - OuterLoop->getHeader()) - << "Only outer loops with induction or reduction PHI nodes can be" - " interchanged currently."; - }); - return true; - } - - Inductions.clear(); - // For multi-level loop nests, make sure that all phi nodes for inner loops - // at all levels can be recognized as a induction or reduction phi. Bail out - // if a phi node at a certain nesting level cannot be properly recognized. - Loop *CurLevelLoop = OuterLoop; - while (!CurLevelLoop->getSubLoops().empty()) { - // We already made sure that the loop nest is tightly nested. - CurLevelLoop = CurLevelLoop->getSubLoops().front(); - if (!findInductionAndReductions(CurLevelLoop, Inductions, nullptr)) { - LLVM_DEBUG( - dbgs() << "Only inner loops with induction or reduction PHI nodes " - << "are supported currently.\n"); - ORE->emit([&]() { - return OptimizationRemarkMissed(DEBUG_TYPE, "UnsupportedPHIInner", - CurLevelLoop->getStartLoc(), - CurLevelLoop->getHeader()) - << "Only inner loops with induction or reduction PHI nodes can be" - " interchange currently."; - }); - return true; - } - } - // TODO: Triangular loops are not handled for now. if (!isLoopStructureUnderstood()) { LLVM_DEBUG(dbgs() << "Loop structure not understood by pass\n"); @@ -1371,16 +1357,6 @@ bool LoopInterchangeLegality::currentLimitations() { return false; } -bool LoopInterchangeLegality::findInductions( - Loop *L, SmallVectorImpl<PHINode *> &Inductions) { - for (PHINode &PHI : L->getHeader()->phis()) { - InductionDescriptor ID; - if (InductionDescriptor::isInductionPHI(&PHI, L, SE, ID)) - Inductions.push_back(&PHI); - } - return !Inductions.empty(); -} - /// We currently only support LCSSA PHI nodes in the inner loop exit if their /// users are either of the following: /// @@ -1526,8 +1502,9 @@ bool LoopInterchangeLegality::canInterchangeLoops(unsigned InnerLoopId, return false; } - if (!findInductions(InnerLoop, InnerLoopInductions)) { - LLVM_DEBUG(dbgs() << "Could not find inner loop induction variables.\n"); + if (!checkInductionsAndReductions(OuterLoop)) { + LLVM_DEBUG(dbgs() << "Failed to find inner loop inductions or found " + "unsupported reductions.\n"); return false; } diff --git a/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll b/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll index 16d42847cf6c2..7b526d05881b8 100644 --- a/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll +++ b/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll @@ -24,7 +24,7 @@ ; CHECK-NEXT: Name: UnsupportedPHIInner ; CHECK-NEXT: Function: reduction_01 ; CHECK-NEXT: Args: -; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchange currently. +; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchanged currently. ; IR-LABEL: @reduction_01( ; IR-NOT: split @@ -82,12 +82,6 @@ exit: ; CHECK-NEXT: Function: reduction_02 ; CHECK-NEXT: Args: ; CHECK-NEXT: - String: Only supports at most one reduction. -; CHECK: --- !Missed -; CHECK-NEXT: Pass: loop-interchange -; CHECK-NEXT: Name: UnsupportedPHIInner -; CHECK-NEXT: Function: reduction_02 -; CHECK-NEXT: Args: -; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchange currently. ; IR-LABEL: @reduction_02( ; IR-NOT: split @@ -151,7 +145,7 @@ exit: ; CHECK-NEXT: Name: UnsupportedPHIInner ; CHECK-NEXT: Function: reduction_03 ; CHECK-NEXT: Args: -; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchange currently. +; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchanged currently. ; IR-LABEL: @reduction_03( ; IR-NOT: split @@ -221,7 +215,7 @@ exit: ; CHECK-NEXT: Name: UnsupportedPHIInner ; CHECK-NEXT: Function: reduction_04 ; CHECK-NEXT: Args: -; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchange currently. +; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchanged currently. ; IR-LABEL: @reduction_04( ; IR-NOT: split @@ -290,7 +284,7 @@ exit: ; CHECK-NEXT: Name: UnsupportedPHIInner ; CHECK-NEXT: Function: reduction_05 ; CHECK-NEXT: Args: -; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchange currently. +; CHECK-NEXT: - String: Only inner loops with induction or reduction PHI nodes can be interchanged currently. ; IR-LABEL: @reduction_05( ; IR-NOT: split _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
