https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/181991
>From 2f708a94a6bc6b26a7d4387efaa713ddd7366c66 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Tue, 17 Feb 2026 10:56:58 +0000 Subject: [PATCH] [LoopInterchange] Fix instorder profitability check --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 91 ++++++++++--------- ...erchangeable-outerloop-multiple-indvars.ll | 2 +- .../profitability-instorder.ll | 70 ++++++++------ 3 files changed, 91 insertions(+), 72 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index aa3bef91d602a..e8a92d8271c86 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1561,53 +1561,62 @@ const DenseMap<const Loop *, unsigned> &CacheCostManager::getCostMap() { return CostMap; } +/// If \S contains an affine addrec for \p L0, store the step recurrence of the +/// addrec in \p Coeff0. Same for \p L1 and \p Coeff1. This function assumes \p +/// S is an nested affine addrec, and it will recursively look through the start +/// value of the addrec to find the coefficients. If the expression is in a +/// complex form, e.g., (addrec + addrec), then the coefficients may not be +/// found. +static void getAddRecCoefficients(ScalarEvolution &SE, const SCEV *S, + const Loop *L0, + std::optional<const SCEV *> &Coeff0, + const Loop *L1, + std::optional<const SCEV *> &Coeff1) { + const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S); + if (!AR) + return; + if (!AR->isAffine()) { + LLVM_DEBUG(dbgs() << "Unexpected non-affine addrec\n"); + return; + } + if (AR->getLoop() == L0) + Coeff0 = AR->getStepRecurrence(SE); + if (AR->getLoop() == L1) + Coeff1 = AR->getStepRecurrence(SE); + getAddRecCoefficients(SE, AR->getStart(), L0, Coeff0, L1, Coeff1); +} + int LoopInterchangeProfitability::getInstrOrderCost() { unsigned GoodOrder, BadOrder; BadOrder = GoodOrder = 0; for (BasicBlock *BB : InnerLoop->blocks()) { for (Instruction &Ins : *BB) { - if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&Ins)) { - bool FoundInnerInduction = false; - bool FoundOuterInduction = false; - for (Value *Op : GEP->operands()) { - // Skip operands that are not SCEV-able. - if (!SE->isSCEVable(Op->getType())) - continue; - - const SCEV *OperandVal = SE->getSCEV(Op); - const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OperandVal); - if (!AR) - continue; + if (!isa<LoadInst, StoreInst>(&Ins)) + continue; + const SCEV *Ptr = SE->getSCEV(getLoadStorePointerOperand(&Ins)); + std::optional<const SCEV *> OuterCoeff, InnerCoeff; + getAddRecCoefficients(*SE, Ptr, OuterLoop, OuterCoeff, InnerLoop, + InnerCoeff); + if (!InnerCoeff.has_value() || !OuterCoeff.has_value()) + continue; - // If we find the inner induction after an outer induction e.g. - // for(int i=0;i<N;i++) - // for(int j=0;j<N;j++) - // A[i][j] = A[i-1][j-1]+k; - // then it is a good order. - if (AR->getLoop() == InnerLoop) { - // We found an InnerLoop induction after OuterLoop induction. It is - // a good order. - FoundInnerInduction = true; - if (FoundOuterInduction) { - GoodOrder++; - break; - } - } - // If we find the outer induction after an inner induction e.g. - // for(int i=0;i<N;i++) - // for(int j=0;j<N;j++) - // A[j][i] = A[j-1][i-1]+k; - // then it is a bad order. - if (AR->getLoop() == OuterLoop) { - // We found an OuterLoop induction after InnerLoop induction. It is - // a bad order. - FoundOuterInduction = true; - if (FoundInnerInduction) { - BadOrder++; - break; - } - } - } + const SCEV *OuterStep = SE->getAbsExpr(*OuterCoeff, /*IsNSW=*/false); + const SCEV *InnerStep = SE->getAbsExpr(*InnerCoeff, /*IsNSW=*/false); + if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, InnerStep, OuterStep)) { + // If we find the inner induction after an outer induction e.g. + // for(int i=0;i<N;i++) + // for(int j=0;j<N;j++) + // A[i][j] = A[i-1][j-1]+k; + // then it is a good order. + GoodOrder++; + } else if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, OuterStep, + InnerStep)) { + // If we find the outer induction after an inner induction e.g. + // for(int i=0;i<N;i++) + // for(int j=0;j<N;j++) + // A[j][i] = A[j-1][i-1]+k; + // then it is a bad order. + BadOrder++; } } } diff --git a/llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll b/llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll index 8cdf999ce45e4..d0e7a52267442 100644 --- a/llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll +++ b/llvm/test/Transforms/LoopInterchange/interchangeable-outerloop-multiple-indvars.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6 -; RUN: opt < %s -passes=loop-interchange -cache-line-size=64 -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s +; RUN: opt < %s -passes=loop-interchange -loop-interchange-profitabilities=ignore -verify-dom-info -verify-loop-info -verify-scev -verify-loop-lcssa -S | FileCheck %s @b = constant [200 x [100 x i32]] zeroinitializer, align 4 @a = constant i32 0, align 4 diff --git a/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll b/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll index 97f8f90f1159f..6501695f0bd79 100644 --- a/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll +++ b/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll @@ -10,24 +10,34 @@ define void @profitable(ptr %A) { ; CHECK-LABEL: define void @profitable( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: [[ENTRY:.*:]] ; CHECK-NEXT: br label %[[LOOP_I_HEADER:.*]] -; CHECK: [[LOOP_I_HEADER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ] +; CHECK: [[LOOP_I_HEADER_PREHEADER:.*]]: ; CHECK-NEXT: br label %[[LOOP_J:.*]] ; CHECK: [[LOOP_J]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[LOOP_I_HEADER]] ], [ [[J_INC:%.*]], %[[LOOP_J]] ] +; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ], [ 0, %[[LOOP_I_HEADER_PREHEADER]] ] +; CHECK-NEXT: br label %[[LOOP_J_SPLIT1:.*]] +; CHECK: [[LOOP_I_HEADER]]: +; CHECK-NEXT: br label %[[LOOP_J1:.*]] +; CHECK: [[LOOP_J1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[LOOP_J_SPLIT:.*]] ], [ 0, %[[LOOP_I_HEADER]] ] +; CHECK-NEXT: br label %[[LOOP_I_HEADER_PREHEADER]] +; CHECK: [[LOOP_J_SPLIT1]]: ; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[J]], 100 ; CHECK-NEXT: [[OFFSET:%.*]] = add i64 [[I]], [[MUL]] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds i8, ptr [[A]], i64 [[OFFSET]] ; CHECK-NEXT: store i8 0, ptr [[GEP]], align 1 -; CHECK-NEXT: [[J_INC]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1 ; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 10 -; CHECK-NEXT: br i1 [[EC_J]], label %[[LOOP_I_LATCH]], label %[[LOOP_J]] +; CHECK-NEXT: br label %[[LOOP_I_LATCH]] +; CHECK: [[LOOP_J_SPLIT]]: +; CHECK-NEXT: [[TMP0]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 10 +; CHECK-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label %[[LOOP_J1]] ; CHECK: [[LOOP_I_LATCH]]: ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 10 -; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[LOOP_I_HEADER]] +; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label %[[LOOP_J]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; @@ -66,25 +76,35 @@ exit: define void @profitable_neg_step(ptr %A) { ; CHECK-LABEL: define void @profitable_neg_step( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: [[ENTRY:.*:]] ; CHECK-NEXT: br label %[[LOOP_I_HEADER:.*]] -; CHECK: [[LOOP_I_HEADER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[ENTRY]] ], [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ] +; CHECK: [[LOOP_I_HEADER_PREHEADER:.*]]: ; CHECK-NEXT: br label %[[LOOP_J:.*]] ; CHECK: [[LOOP_J]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[LOOP_I_HEADER]] ], [ [[J_INC:%.*]], %[[LOOP_J]] ] +; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ], [ 0, %[[LOOP_I_HEADER_PREHEADER]] ] +; CHECK-NEXT: br label %[[LOOP_J_SPLIT1:.*]] +; CHECK: [[LOOP_I_HEADER]]: +; CHECK-NEXT: br label %[[LOOP_J1:.*]] +; CHECK: [[LOOP_J1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[LOOP_J_SPLIT:.*]] ], [ 0, %[[LOOP_I_HEADER]] ] +; CHECK-NEXT: br label %[[LOOP_I_HEADER_PREHEADER]] +; CHECK: [[LOOP_J_SPLIT1]]: ; CHECK-NEXT: [[J_REV:%.*]] = sub i64 9, [[J]] ; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[J_REV]], 100 ; CHECK-NEXT: [[OFFSET:%.*]] = add i64 [[I]], [[MUL]] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds i8, ptr [[A]], i64 [[OFFSET]] ; CHECK-NEXT: store i8 0, ptr [[GEP]], align 1 -; CHECK-NEXT: [[J_INC]] = add i64 [[J]], 1 +; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1 ; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 10 -; CHECK-NEXT: br i1 [[EC_J]], label %[[LOOP_I_LATCH]], label %[[LOOP_J]] +; CHECK-NEXT: br label %[[LOOP_I_LATCH]] +; CHECK: [[LOOP_J_SPLIT]]: +; CHECK-NEXT: [[TMP0]] = add i64 [[J]], 1 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 10 +; CHECK-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label %[[LOOP_J1]] ; CHECK: [[LOOP_I_LATCH]]: ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 10 -; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[LOOP_I_HEADER]] +; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label %[[LOOP_J]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; @@ -124,34 +144,24 @@ exit: define void @unprofitable(ptr %A) { ; CHECK-LABEL: define void @unprofitable( ; CHECK-SAME: ptr [[A:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[LOOP_J_PREHEADER:.*]] -; CHECK: [[LOOP_I_HEADER_PREHEADER:.*]]: +; CHECK-NEXT: [[LOOP_I_HEADER_PREHEADER:.*]]: ; CHECK-NEXT: br label %[[LOOP_I_HEADER:.*]] ; CHECK: [[LOOP_I_HEADER]]: -; CHECK-NEXT: [[I:%.*]] = phi i64 [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ], [ 0, %[[LOOP_I_HEADER_PREHEADER]] ] +; CHECK-NEXT: [[I:%.*]] = phi i64 [ 0, %[[LOOP_I_HEADER_PREHEADER]] ], [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ] ; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[I]], 100 ; CHECK-NEXT: br label %[[LOOP_J_SPLIT1:.*]] -; CHECK: [[LOOP_J_PREHEADER]]: -; CHECK-NEXT: br label %[[LOOP_J:.*]] -; CHECK: [[LOOP_J]]: -; CHECK-NEXT: [[J:%.*]] = phi i64 [ [[TMP0:%.*]], %[[LOOP_J_SPLIT:.*]] ], [ 0, %[[LOOP_J_PREHEADER]] ] -; CHECK-NEXT: br label %[[LOOP_I_HEADER_PREHEADER]] ; CHECK: [[LOOP_J_SPLIT1]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[LOOP_I_HEADER]] ], [ [[TMP0:%.*]], %[[LOOP_J_SPLIT1]] ] ; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds [1 x i8], ptr [[A]], i64 [[J]], i64 [[MUL]] ; CHECK-NEXT: store i8 0, ptr [[GEP]], align 1 -; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 10 -; CHECK-NEXT: br label %[[LOOP_I_LATCH]] -; CHECK: [[LOOP_J_SPLIT]]: ; CHECK-NEXT: [[TMP0]] = add i64 [[J]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i64 [[TMP0]], 10 -; CHECK-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label %[[LOOP_J]] +; CHECK-NEXT: br i1 [[TMP1]], label %[[LOOP_I_LATCH]], label %[[LOOP_J_SPLIT1]] ; CHECK: [[LOOP_I_LATCH]]: ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 10 -; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label %[[LOOP_I_HEADER]] -; CHECK: [[EXIT]]: +; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT:.*]], label %[[LOOP_I_HEADER]] +; CHECK: [[LOOP_J_SPLIT]]: ; CHECK-NEXT: ret void ; entry: _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
