https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/202751
>From 4b445c6f2fe34d826d7adf664c7a5ca179690b8a Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Thu, 11 Jun 2026 06:02:24 +0000 Subject: [PATCH 1/2] [LoopInterchange] Consolidate induction and reduction vars check --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 171 ++++++++---------- .../reduction2mem-limitation.ll | 6 - 2 files changed, 78 insertions(+), 99 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index f0cf9d6d4724f..0a47c36e300fb 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 inner loop (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 inner loop; otherwise, return true. + bool checkInductionsAndReductions(Loop *OuterLoop); /// Detect and record the reduction of the inner loop. Add them to /// InnerReductions. @@ -1239,32 +1239,33 @@ 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 *CurLoop = OuterLoop; + for (unsigned Depth = 0; CurLoop; ++Depth, CurLoop = ChildLoop(CurLoop)) { + for (PHINode &PHI : CurLoop->getHeader()->phis()) { + InductionDescriptor ID; + if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) { + if (Depth == 1) + InnerLoopInductions.push_back(&PHI); + continue; + } + + if (Depth == 0) { + Loop *OuterLoop = CurLoop; + Loop *InnerLoop = ChildLoop(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,23 +1273,54 @@ 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" + " interchange 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; + if (Depth == 1 && InnerLoopInductions.empty()) { + LLVM_DEBUG(dbgs() << "Could not find inner loop induction variables.\n"); + 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; @@ -1318,44 +1350,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 +1365,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 +1510,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..46c911d5fa1ac 100644 --- a/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll +++ b/llvm/test/Transforms/LoopInterchange/reduction2mem-limitation.ll @@ -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 >From e1e5b37849185c34687ee4db99cfbdd197b55946 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 10 Jun 2026 04:41:33 +0900 Subject: [PATCH 2/2] [LoopInterchange] Reject if inner loop IV has outer-variant step --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 8 ++- .../inner-induciton-step-is-not-invariant.ll | 68 ++++++------------- 2 files changed, 27 insertions(+), 49 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 0a47c36e300fb..4b88bd1dc7649 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1251,8 +1251,14 @@ bool LoopInterchangeLegality::checkInductionsAndReductions(Loop *OuterLoop) { for (PHINode &PHI : CurLoop->getHeader()->phis()) { InductionDescriptor ID; if (InductionDescriptor::isInductionPHI(&PHI, CurLoop, SE, ID)) { - if (Depth == 1) + if (Depth == 1) { + const SCEV *Step = ID.getStep(); + if (!SE->isLoopInvariant(Step, OuterLoop)) { + InnerLoopInductions.clear(); + return false; + } InnerLoopInductions.push_back(&PHI); + } continue; } diff --git a/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll b/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll index 37bc9266942ed..f5960c7400cc8 100644 --- a/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll +++ b/llvm/test/Transforms/LoopInterchange/inner-induciton-step-is-not-invariant.ll @@ -10,43 +10,29 @@ ; for (j = 0, k = 0; k < 16 + i; j++, k += i) ; A[8*j + i] += 1; ; -; FIXME: This is now interchanged. -; define void @step_of_k_is_i_0(ptr %A) { ; CHECK-LABEL: define void @step_of_k_is_i_0( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] -; CHECK: [[OUTER_HEADER_PREHEADER:.*]]: -; CHECK-NEXT: br label %[[INNER:.*]] -; CHECK: [[INNER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 1, %[[OUTER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] -; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[OUTER_HEADER:.*]]: ; CHECK-NEXT: br label %[[INNER1:.*]] ; CHECK: [[INNER1]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER]] -; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 1, %[[OUTER_HEADER]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[J_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[K:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[K_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr [8 x i8], ptr [[A]], i64 [[J]], i64 [[I]] ; CHECK-NEXT: [[OLD:%.*]] = load i8, ptr [[GEP]], align 1 ; CHECK-NEXT: [[NEW:%.*]] = add i8 [[OLD]], 1 ; CHECK-NEXT: store i8 [[NEW]], ptr [[GEP]], align 1 -; CHECK-NEXT: [[J_NEXT:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[K_NEXT:%.*]] = add i64 [[K]], [[I]] -; CHECK-NEXT: [[EC_INNER_NOT:%.*]] = icmp slt i64 [[K]], 16 -; CHECK-NEXT: br label %[[OUTER_LATCH]] -; CHECK: [[INNER_SPLIT]]: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i64 [ [[I]], %[[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP0]] = add i64 [[K]], [[I_LCSSA]] -; CHECK-NEXT: [[TMP1]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1 +; CHECK-NEXT: [[K_NEXT]] = add i64 [[K]], [[I]] ; CHECK-NEXT: [[TMP2:%.*]] = icmp slt i64 [[K]], 16 -; CHECK-NEXT: br i1 [[TMP2]], label %[[INNER1]], label %[[EXIT:.*]] +; CHECK-NEXT: br i1 [[TMP2]], label %[[OUTER_HEADER_PREHEADER]], label %[[OUTER_LATCH]] ; CHECK: [[OUTER_LATCH]]: ; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 ; CHECK-NEXT: [[CMP_I:%.*]] = icmp slt i64 [[I_NEXT]], 8 -; CHECK-NEXT: br i1 [[CMP_I]], label %[[INNER]], label %[[INNER_SPLIT]] +; CHECK-NEXT: br i1 [[CMP_I]], label %[[INNER1]], label %[[EXIT:.*]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; @@ -82,41 +68,27 @@ exit: ; for (j = 0, k = 0; j < 30; j++, k += i) ; A[i][j] = k; ; -; FIXME: This is now interchanged. -; define void @step_ok_k_is_i_1(ptr %A) { ; CHECK-LABEL: define void @step_ok_k_is_i_1( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[OUTER_HEADER:.*]] -; CHECK: [[OUTER_HEADER_PREHEADER:.*]]: -; CHECK-NEXT: br label %[[INNER:.*]] -; CHECK: [[INNER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ], [ 0, %[[OUTER_HEADER_PREHEADER]] ] -; CHECK-NEXT: br label %[[INNER_SPLIT1:.*]] -; CHECK: [[OUTER_HEADER]]: +; CHECK-NEXT: [[OUTER_HEADER:.*]]: ; CHECK-NEXT: br label %[[INNER1:.*]] ; CHECK: [[INNER1]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP1:%.*]], %[[INNER_SPLIT:.*]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: [[K:%.*]] = phi i64 [ [[TMP0:%.*]], %[[INNER_SPLIT]] ], [ 0, %[[OUTER_HEADER]] ] -; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER]] -; CHECK: [[INNER_SPLIT1]]: +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[OUTER_HEADER]] ], [ [[I_NEXT:%.*]], %[[OUTER_LATCH:.*]] ] +; CHECK-NEXT: br label %[[OUTER_HEADER_PREHEADER:.*]] +; CHECK: [[OUTER_HEADER_PREHEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[J_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[K:%.*]] = phi i64 [ 0, %[[INNER1]] ], [ [[K_NEXT:%.*]], %[[OUTER_HEADER_PREHEADER]] ] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds [40 x i64], ptr [[A]], i64 [[I]], i64 [[J]] ; CHECK-NEXT: store i64 [[K]], ptr [[GEP]], align 4 -; CHECK-NEXT: [[J_NEXT:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[K_NEXT:%.*]] = add i64 [[K]], [[I]] -; CHECK-NEXT: [[EC_INNER:%.*]] = icmp eq i64 [[J]], 30 -; CHECK-NEXT: br label %[[OUTER_LATCH]] -; CHECK: [[INNER_SPLIT]]: -; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i64 [ [[I]], %[[OUTER_LATCH]] ] -; CHECK-NEXT: [[TMP0]] = add i64 [[K]], [[I_LCSSA]] -; CHECK-NEXT: [[TMP1]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_NEXT]] = add i64 [[J]], 1 +; CHECK-NEXT: [[K_NEXT]] = add i64 [[K]], [[I]] ; CHECK-NEXT: [[TMP2:%.*]] = icmp eq i64 [[J]], 30 -; CHECK-NEXT: br i1 [[TMP2]], label %[[EXIT:.*]], label %[[INNER1]] +; CHECK-NEXT: br i1 [[TMP2]], label %[[OUTER_LATCH]], label %[[OUTER_HEADER_PREHEADER]] ; CHECK: [[OUTER_LATCH]]: ; CHECK-NEXT: [[I_NEXT]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_NEXT]], 6 -; CHECK-NEXT: br i1 [[EC_I]], label %[[INNER_SPLIT]], label %[[INNER]] +; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[INNER1]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
