https://github.com/kasuga-fj updated https://github.com/llvm/llvm-project/pull/193477
>From 6a9a4e790a73a14f8255345ed0ac899abc826ee7 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Wed, 22 Apr 2026 10:32:00 +0000 Subject: [PATCH 1/2] [LoopInterchange] Take base pointer into account in profitability check --- .../lib/Transforms/Scalar/LoopInterchange.cpp | 25 +++++++++++++------ .../profitability-instorder.ll | 24 ++++++------------ 2 files changed, 25 insertions(+), 24 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 35d2716f74dd7..48fb0836c4d7d 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1640,17 +1640,19 @@ std::optional<const SCEV *> getAddRecCoefficient(ScalarEvolution &SE, } int LoopInterchangeProfitability::getInstrOrderCost() { - unsigned GoodOrder, BadOrder; - BadOrder = GoodOrder = 0; + // Map from the base pointer fo an acess to a pair of booleans indicating + // whether we find good or bad order. + DenseMap<const SCEV *, std::pair<bool, bool>> BasePtr2Score; for (BasicBlock *BB : InnerLoop->blocks()) { for (Instruction &Ins : *BB) { if (!isa<LoadInst, StoreInst>(&Ins)) continue; - const SCEV *Ptr = SE->getSCEV(getLoadStorePointerOperand(&Ins)); + const SCEV *Access = SE->getSCEV(getLoadStorePointerOperand(&Ins)); + const SCEV *BasePtr = SE->getPointerBase(Access); std::optional<const SCEV *> OuterCoeff = - getAddRecCoefficient(*SE, Ptr, OuterLoop); + getAddRecCoefficient(*SE, Access, OuterLoop); std::optional<const SCEV *> InnerCoeff = - getAddRecCoefficient(*SE, Ptr, InnerLoop); + getAddRecCoefficient(*SE, Access, InnerLoop); if (!OuterCoeff.has_value() || !*OuterCoeff || !InnerCoeff.has_value() || !*InnerCoeff) @@ -1680,11 +1682,20 @@ int LoopInterchangeProfitability::getInstrOrderCost() { // // then it is a bad order. if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, InnerStep, OuterStep)) - GoodOrder++; + BasePtr2Score[BasePtr].first = true; else if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, OuterStep, InnerStep)) - BadOrder++; + BasePtr2Score[BasePtr].second = true; } } + + int GoodOrder = 0, BadOrder = 0; + for (const auto &[BasePtr, Score] : BasePtr2Score) { + auto [Good, Bad] = Score; + if (Good) + GoodOrder++; + if (Bad) + BadOrder++; + } return GoodOrder - BadOrder; } diff --git a/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll b/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll index 9479eaa00a1f0..c69a75c63e2da 100644 --- a/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll +++ b/llvm/test/Transforms/LoopInterchange/profitability-instorder.ll @@ -198,19 +198,13 @@ exit: define void @unprofitable1(ptr noalias %A, ptr noalias %B, ptr noalias %C) { ; CHECK-LABEL: define void @unprofitable1( ; CHECK-SAME: ptr noalias [[A:%.*]], ptr noalias [[B:%.*]], ptr noalias [[C:%.*]]) { -; CHECK-NEXT: [[ENTRY:.*:]] -; CHECK-NEXT: br label %[[LOOP_J_PREHEADER:.*]] -; CHECK: [[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: br label %[[LOOP_J_SPLIT1:.*]] -; CHECK: [[LOOP_J_PREHEADER]]: +; CHECK-NEXT: [[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: [[I:%.*]] = phi i64 [ 0, %[[LOOP_J_PREHEADER]] ], [ [[I_INC:%.*]], %[[LOOP_I_LATCH:.*]] ] +; CHECK-NEXT: br label %[[LOOP_I_HEADER_PREHEADER:.*]] +; CHECK: [[LOOP_I_HEADER_PREHEADER]]: +; CHECK-NEXT: [[J:%.*]] = phi i64 [ 0, %[[LOOP_J]] ], [ [[TMP0:%.*]], %[[LOOP_I_HEADER_PREHEADER]] ] ; CHECK-NEXT: [[GEP_A:%.*]] = getelementptr inbounds [100 x i8], ptr [[A]], i64 [[I]], i64 [[J]] ; CHECK-NEXT: [[GEP_B:%.*]] = getelementptr inbounds [100 x i8], ptr [[B]], i64 [[I]], i64 [[J]] ; CHECK-NEXT: [[GEP_C0:%.*]] = getelementptr inbounds [100 x i8], ptr [[C]], i64 [[J]], i64 [[I]] @@ -224,17 +218,13 @@ define void @unprofitable1(ptr noalias %A, ptr noalias %B, ptr noalias %C) { ; CHECK-NEXT: [[SUM_1:%.*]] = add i8 [[SUM_0]], [[VAL_C1]] ; CHECK-NEXT: [[SUM_2:%.*]] = add i8 [[SUM_1]], [[VAL_C2]] ; CHECK-NEXT: store i8 [[SUM_2]], ptr [[GEP_A]], align 1 -; CHECK-NEXT: [[J_INC:%.*]] = add i64 [[J]], 1 -; CHECK-NEXT: [[EC_J:%.*]] = icmp eq i64 [[J_INC]], 42 -; 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]], 42 -; CHECK-NEXT: br i1 [[TMP1]], label %[[EXIT:.*]], label %[[LOOP_J]] +; CHECK-NEXT: br i1 [[TMP1]], label %[[LOOP_I_LATCH]], label %[[LOOP_I_HEADER_PREHEADER]] ; CHECK: [[LOOP_I_LATCH]]: ; CHECK-NEXT: [[I_INC]] = add i64 [[I]], 1 ; CHECK-NEXT: [[EC_I:%.*]] = icmp eq i64 [[I_INC]], 42 -; CHECK-NEXT: br i1 [[EC_I]], label %[[LOOP_J_SPLIT]], label %[[LOOP_I_HEADER]] +; CHECK-NEXT: br i1 [[EC_I]], label %[[EXIT:.*]], label %[[LOOP_J]] ; CHECK: [[EXIT]]: ; CHECK-NEXT: ret void ; >From fbd8a187e8306171a28d38f55ed1148c97ab2cc0 Mon Sep 17 00:00:00 2001 From: Ryotaro Kasuga <[email protected]> Date: Tue, 19 May 2026 12:04:10 +0000 Subject: [PATCH 2/2] update impl --- llvm/lib/Transforms/Scalar/LoopInterchange.cpp | 18 +++++------------- 1 file changed, 5 insertions(+), 13 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 48fb0836c4d7d..bd09ca12f338a 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -1640,9 +1640,7 @@ std::optional<const SCEV *> getAddRecCoefficient(ScalarEvolution &SE, } int LoopInterchangeProfitability::getInstrOrderCost() { - // Map from the base pointer fo an acess to a pair of booleans indicating - // whether we find good or bad order. - DenseMap<const SCEV *, std::pair<bool, bool>> BasePtr2Score; + SmallPtrSet<const SCEV *, 4> GoodBasePtrs, BadBasePtrs; for (BasicBlock *BB : InnerLoop->blocks()) { for (Instruction &Ins : *BB) { if (!isa<LoadInst, StoreInst>(&Ins)) @@ -1682,20 +1680,14 @@ int LoopInterchangeProfitability::getInstrOrderCost() { // // then it is a bad order. if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, InnerStep, OuterStep)) - BasePtr2Score[BasePtr].first = true; + GoodBasePtrs.insert(BasePtr); else if (SE->isKnownPredicate(ICmpInst::ICMP_SLT, OuterStep, InnerStep)) - BasePtr2Score[BasePtr].second = true; + BadBasePtrs.insert(BasePtr); } } - int GoodOrder = 0, BadOrder = 0; - for (const auto &[BasePtr, Score] : BasePtr2Score) { - auto [Good, Bad] = Score; - if (Good) - GoodOrder++; - if (Bad) - BadOrder++; - } + int GoodOrder = GoodBasePtrs.size(); + int BadOrder = BadBasePtrs.size(); return GoodOrder - BadOrder; } _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
