https://github.com/skachkov-sc updated https://github.com/llvm/llvm-project/pull/140722
>From b08f1f89c1e8b8dd2acb0662fa1da021f27d9ab9 Mon Sep 17 00:00:00 2001 From: Sergey Kachkov <[email protected]> Date: Mon, 10 Nov 2025 16:35:23 +0300 Subject: [PATCH 1/2] [IVDescriptors] Add unit tests for MonotonicDescriptor --- llvm/unittests/Analysis/IVDescriptorsTest.cpp | 131 ++++++++++++++++++ 1 file changed, 131 insertions(+) diff --git a/llvm/unittests/Analysis/IVDescriptorsTest.cpp b/llvm/unittests/Analysis/IVDescriptorsTest.cpp index 453800abf9cab..5e31a2bde7e7d 100644 --- a/llvm/unittests/Analysis/IVDescriptorsTest.cpp +++ b/llvm/unittests/Analysis/IVDescriptorsTest.cpp @@ -10,6 +10,7 @@ #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" @@ -259,3 +260,133 @@ for.end: EXPECT_EQ(Kind, RecurKind::FMax); }); } + +TEST(IVDescriptorsTest, MonotonicIntVar) { + // Parse the module. + LLVMContext Context; + + std::unique_ptr<Module> M = + parseIR(Context, + R"(define void @foo(i32 %start, i1 %cond, i64 %n) { +entry: + br label %for.body + +for.body: + %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ] + %monotonic = phi i32 [ %start, %entry ], [ %monotonic.next, %for.inc ] + br i1 %cond, label %if.then, label %for.inc + +if.then: + %inc = add nsw i32 %monotonic, 1 + br label %for.inc + +for.inc: + %monotonic.next = phi i32 [ %inc, %if.then ], [ %monotonic, %for.body ] + %i.next = add nuw nsw i64 %i, 1 + %exitcond.not = icmp eq i64 %i.next, %n + br i1 %exitcond.not, label %for.end, label %for.body + +for.end: + ret void +})"); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // First basic block is entry - skip it. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.body"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + BasicBlock::iterator BBI = Header->begin(); + assert((&*BBI)->getName() == "i"); + PHINode *Phi = dyn_cast<PHINode>(&*(++BBI)); + assert(Phi->getName() == "monotonic"); + BasicBlock *IfThen = &*(++FI); + assert(IfThen->getName() == "if.then"); + Instruction *StepInst = &*(IfThen->begin()); + assert(StepInst->getName() == "inc"); + BasicBlock *IfEnd = &*(++FI); + assert(IfEnd->getName() == "for.inc"); + auto *ChainPhi = dyn_cast<PHINode>(&*(IfEnd->begin())); + assert(ChainPhi->getName() == "monotonic.next"); + MonotonicDescriptor Desc; + bool IsMonotonicPhi = + MonotonicDescriptor::isMonotonicPHI(Phi, L, Desc, SE); + EXPECT_TRUE(IsMonotonicPhi); + auto &Chain = Desc.getChain(); + EXPECT_TRUE(Chain.size() == 1 && Chain.contains(ChainPhi)); + EXPECT_EQ(Desc.getStepInst(), StepInst); + EXPECT_EQ(Desc.getPredicateEdge(), + MonotonicDescriptor::Edge(IfThen, IfEnd)); + auto *StartSCEV = SE.getSCEV(F.getArg(0)); + auto *StepSCEV = SE.getConstant(StartSCEV->getType(), 1); + EXPECT_EQ(Desc.getExpr(), + SE.getAddRecExpr(StartSCEV, StepSCEV, L, SCEV::FlagNW)); + }); +} + +TEST(IVDescriptorsTest, MonotonicPtrVar) { + // Parse the module. + LLVMContext Context; + + std::unique_ptr<Module> M = + parseIR(Context, + R"(define void @foo(ptr %start, i1 %cond, i64 %n) { +entry: + br label %for.body + +for.body: + %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ] + %monotonic = phi ptr [ %start, %entry ], [ %monotonic.next, %for.inc ] + br i1 %cond, label %if.then, label %for.inc + +if.then: + %inc = getelementptr inbounds i8, ptr %monotonic, i64 4 + br label %for.inc + +for.inc: + %monotonic.next = phi ptr [ %inc, %if.then ], [ %monotonic, %for.body ] + %i.next = add nuw nsw i64 %i, 1 + %exitcond.not = icmp eq i64 %i.next, %n + br i1 %exitcond.not, label %for.end, label %for.body + +for.end: + ret void +})"); + + runWithLoopInfoAndSE( + *M, "foo", [&](Function &F, LoopInfo &LI, ScalarEvolution &SE) { + Function::iterator FI = F.begin(); + // First basic block is entry - skip it. + BasicBlock *Header = &*(++FI); + assert(Header->getName() == "for.body"); + Loop *L = LI.getLoopFor(Header); + EXPECT_NE(L, nullptr); + BasicBlock::iterator BBI = Header->begin(); + assert((&*BBI)->getName() == "i"); + PHINode *Phi = dyn_cast<PHINode>(&*(++BBI)); + assert(Phi->getName() == "monotonic"); + BasicBlock *IfThen = &*(++FI); + assert(IfThen->getName() == "if.then"); + Instruction *StepInst = &*(IfThen->begin()); + assert(StepInst->getName() == "inc"); + BasicBlock *IfEnd = &*(++FI); + assert(IfEnd->getName() == "for.inc"); + auto *ChainPhi = dyn_cast<PHINode>(&*(IfEnd->begin())); + assert(ChainPhi->getName() == "monotonic.next"); + MonotonicDescriptor Desc; + bool IsMonotonicPhi = + MonotonicDescriptor::isMonotonicPHI(Phi, L, Desc, SE); + EXPECT_TRUE(IsMonotonicPhi); + auto &Chain = Desc.getChain(); + EXPECT_TRUE(Chain.size() == 1 && Chain.contains(ChainPhi)); + EXPECT_EQ(Desc.getStepInst(), StepInst); + EXPECT_EQ(Desc.getPredicateEdge(), + MonotonicDescriptor::Edge(IfThen, IfEnd)); + auto *StartSCEV = SE.getSCEV(F.getArg(0)); + auto *StepSCEV = SE.getConstant(StartSCEV->getType(), 4); + EXPECT_EQ(Desc.getExpr(), + SE.getAddRecExpr(StartSCEV, StepSCEV, L, SCEV::FlagNW)); + }); +} >From f39e2a031d2bc26caa669b753c03357df4b5b8ac Mon Sep 17 00:00:00 2001 From: Sergey Kachkov <[email protected]> Date: Wed, 22 Nov 2023 17:24:08 +0300 Subject: [PATCH 2/2] [LoopVectorize][NFC] Refactor widening decision logic --- .../Transforms/Vectorize/LoopVectorize.cpp | 52 +++++++++---------- 1 file changed, 24 insertions(+), 28 deletions(-) diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index 906fa2f857c21..e069b2e8103e0 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1240,9 +1240,10 @@ class LoopVectorizationCostModel { getDivRemSpeculationCost(Instruction *I, ElementCount VF) const; - /// Returns true if \p I is a memory instruction with consecutive memory - /// access that can be widened. - bool memoryInstructionCanBeWidened(Instruction *I, ElementCount VF); + /// Returns widening decision (CM_Widen or CM_Widen_Reverse) if \p I is a + /// memory instruction with consecutive access that can be widened, or + /// CM_Unknown otherwise. + InstWidening memoryInstructionCanBeWidened(Instruction *I, ElementCount VF); /// Returns true if \p I is a memory instruction in an interleaved-group /// of memory accesses that can be vectorized with wide vector loads/stores @@ -1509,7 +1510,8 @@ class LoopVectorizationCostModel { /// The cost computation for widening instruction \p I with consecutive /// memory access. - InstructionCost getConsecutiveMemOpCost(Instruction *I, ElementCount VF); + InstructionCost getConsecutiveMemOpCost(Instruction *I, ElementCount VF, + InstWidening Decision); /// The cost calculation for Load/Store instruction \p I with uniform pointer - /// Load: scalar load + broadcast. @@ -2988,8 +2990,9 @@ bool LoopVectorizationCostModel::interleavedAccessCanBeWidened( : TTI.isLegalMaskedStore(Ty, Alignment, AS); } -bool LoopVectorizationCostModel::memoryInstructionCanBeWidened( - Instruction *I, ElementCount VF) { +LoopVectorizationCostModel::InstWidening +LoopVectorizationCostModel::memoryInstructionCanBeWidened(Instruction *I, + ElementCount VF) { // Get and ensure we have a valid memory instruction. assert((isa<LoadInst, StoreInst>(I)) && "Invalid memory instruction"); @@ -2997,21 +3000,23 @@ bool LoopVectorizationCostModel::memoryInstructionCanBeWidened( auto *ScalarTy = getLoadStoreType(I); // In order to be widened, the pointer should be consecutive, first of all. - if (!Legal->isConsecutivePtr(ScalarTy, Ptr)) - return false; + auto Stride = Legal->isConsecutivePtr(ScalarTy, Ptr); + if (!Stride) + return CM_Unknown; + assert((Stride == 1 || Stride == -1) && "Expected consecutive stride."); // If the instruction is a store located in a predicated block, it will be // scalarized. if (isScalarWithPredication(I, VF)) - return false; + return CM_Unknown; // If the instruction's allocated size doesn't equal it's type size, it // requires padding and will be scalarized. auto &DL = I->getDataLayout(); if (hasIrregularType(ScalarTy, DL)) - return false; + return CM_Unknown; - return true; + return Stride == 1 ? CM_Widen : CM_Widen_Reverse; } void LoopVectorizationCostModel::collectLoopUniforms(ElementCount VF) { @@ -5183,17 +5188,14 @@ LoopVectorizationCostModel::getMemInstScalarizationCost(Instruction *I, return Cost; } -InstructionCost -LoopVectorizationCostModel::getConsecutiveMemOpCost(Instruction *I, - ElementCount VF) { +InstructionCost LoopVectorizationCostModel::getConsecutiveMemOpCost( + Instruction *I, ElementCount VF, InstWidening Decision) { Type *ValTy = getLoadStoreType(I); auto *VectorTy = cast<VectorType>(toVectorTy(ValTy, VF)); - Value *Ptr = getLoadStorePointerOperand(I); unsigned AS = getLoadStoreAddressSpace(I); - int ConsecutiveStride = Legal->isConsecutivePtr(ValTy, Ptr); - assert((ConsecutiveStride == 1 || ConsecutiveStride == -1) && - "Stride should be 1 or -1 for consecutive memory access"); + assert((Decision == CM_Widen || Decision == CM_Widen_Reverse) && + "Expected widen decision."); const Align Alignment = getLoadStoreAlignment(I); InstructionCost Cost = 0; if (Legal->isMaskRequired(I)) { @@ -5205,8 +5207,7 @@ LoopVectorizationCostModel::getConsecutiveMemOpCost(Instruction *I, CostKind, OpInfo, I); } - bool Reverse = ConsecutiveStride < 0; - if (Reverse) + if (Decision == CM_Widen_Reverse) Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Reverse, VectorTy, VectorTy, {}, CostKind, 0); return Cost; @@ -5617,14 +5618,9 @@ void LoopVectorizationCostModel::setCostBasedWideningDecision(ElementCount VF) { } // We assume that widening is the best solution when possible. - if (memoryInstructionCanBeWidened(&I, VF)) { - InstructionCost Cost = getConsecutiveMemOpCost(&I, VF); - int ConsecutiveStride = Legal->isConsecutivePtr( - getLoadStoreType(&I), getLoadStorePointerOperand(&I)); - assert((ConsecutiveStride == 1 || ConsecutiveStride == -1) && - "Expected consecutive stride."); - InstWidening Decision = - ConsecutiveStride == 1 ? CM_Widen : CM_Widen_Reverse; + if (auto Decision = memoryInstructionCanBeWidened(&I, VF); + Decision != CM_Unknown) { + InstructionCost Cost = getConsecutiveMemOpCost(&I, VF, Decision); setWideningDecision(&I, VF, Decision, Cost); continue; } _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
