https://github.com/gandhi56 updated https://github.com/llvm/llvm-project/pull/205249
>From 71ad5da0634dd1165854cb4351fd8438a2712c37 Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Thu, 2 Jul 2026 13:22:06 -0400 Subject: [PATCH 1/6] [SandboxIR] Fix pass pipeline parsing after aux arguments After parsing a pass aux argument, resume scanning pass names instead of args when the next token is a delimiter. This allows flat pipelines like foo(aux),bar to be parsed correctly. Co-authored-by: Cursor <[email protected]> --- llvm/include/llvm/SandboxIR/PassManager.h | 9 +++++++-- llvm/unittests/SandboxIR/PassTest.cpp | 16 ++++++++++++++++ 2 files changed, 23 insertions(+), 2 deletions(-) diff --git a/llvm/include/llvm/SandboxIR/PassManager.h b/llvm/include/llvm/SandboxIR/PassManager.h index 5b9b4d0562e6d..057f61096e4ce 100644 --- a/llvm/include/llvm/SandboxIR/PassManager.h +++ b/llvm/include/llvm/SandboxIR/PassManager.h @@ -235,9 +235,14 @@ class PassManager : public ParentPass { } break; case State::AuxArgsEnded: - if (C == EndToken || C == PassDelimToken) { + if (C == EndToken) { AddPass(PassName, StringRef(), AuxArg); - CurrentState = State::ScanArgs; + CurrentState = State::ScanName; + } else if (C == PassDelimToken) { + AddPass(PassName, StringRef(), AuxArg); + PassBeginIdx = Idx + 1; + AuxArg = StringRef(); + CurrentState = State::ScanName; } else if (C == BeginArgsToken) { ++NestedArgs; ArgsBeginIdx = Idx + 1; diff --git a/llvm/unittests/SandboxIR/PassTest.cpp b/llvm/unittests/SandboxIR/PassTest.cpp index 4707137645430..f0931ad66468e 100644 --- a/llvm/unittests/SandboxIR/PassTest.cpp +++ b/llvm/unittests/SandboxIR/PassTest.cpp @@ -323,6 +323,22 @@ define void @f() { EXPECT_EQ(Str, "foo(aux1)<abc>bar<nested1(aux2)<nested2<nested3()>>>foo(aux3)<>"); + // A pass with an aux argument followed by another pass in a flat pipeline. + std::string AuxArgStr; + auto CreatePassWithAuxArg = + [&AuxArgStr](llvm::StringRef Name, llvm::StringRef Args, + llvm::StringRef AuxArg) -> std::unique_ptr<FunctionPass> { + if (Name == "foo") + return std::make_unique<FooPass>(AuxArgStr, Args, AuxArg); + if (Name == "bar") + return std::make_unique<BarPass>(AuxArgStr, Args, AuxArg); + return nullptr; + }; + FunctionPassManager FPMWithAuxArg("test-fpm"); + FPMWithAuxArg.setPassPipeline("foo(aux1),bar", CreatePassWithAuxArg); + FPMWithAuxArg.runOnFunction(*F, Analyses::emptyForTesting()); + EXPECT_EQ(AuxArgStr, "foo(aux1)<>bar<>"); + // A second call to setPassPipeline will trigger an assertion in debug mode. #ifndef NDEBUG EXPECT_DEATH(FPM.setPassPipeline("bar,bar,foo", CreatePass), >From 049aa3430cb7c2a7d85ace52383e5a67b878bb9d Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Sun, 14 Jun 2026 17:01:48 -0400 Subject: [PATCH 2/6] [SBVec] Implement topDown/botUp vectorizers in unison This patch introduces the `top-down-vec` pass to the Sandbox Vectorizer, adding the ability to traverse use-def chains top-down to discover and collect vectorization opportunities. Furthermore, this patch unifies the two vectorizers into a single implementation to minimize code duplication. Co-authored-by: Cursor <[email protected]> --- .../SandboxVectorizer/Passes/BottomUpVec.h | 28 +- .../SandboxVectorizer/Passes/BottomUpVec.cpp | 179 +++++++++-- .../SandboxVectorizer/Passes/PassRegistry.def | 1 + .../SandboxVectorizer/external_uses.ll | 52 ++- .../test/Transforms/SandboxVectorizer/pack.ll | 79 ++++- .../SandboxVectorizer/topdown_vec.ll | 304 ++++++++++++++++++ 6 files changed, 607 insertions(+), 36 deletions(-) create mode 100644 llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h index 50ac1ecbf9f23..680e04b5dc2ee 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h @@ -6,7 +6,8 @@ // //===----------------------------------------------------------------------===// // -// A Bottom-Up Vectorizer pass. +// A bottom-up vectorizer pass. TopDownVec reuses this implementation with a +// different traversal direction. // #ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H @@ -22,6 +23,8 @@ namespace llvm::sandboxir { +enum class VecDirection { TopDown, BottomUp }; + /// This is a simple bottom-up vectorizer Region pass. /// It expects a "seed slice" as an input in the Region's Aux vector. /// The "seed slice" is a vector of instructions that can be used as a starting @@ -32,7 +35,10 @@ namespace llvm::sandboxir { /// profitable or not. For now profitability is checked at the end of the region /// pass pipeline by a dedicated pass that accepts or rejects the IR /// transaction, depending on the cost. -class LLVM_ABI BottomUpVec final : public RegionPass { +class LLVM_ABI BottomUpVec : public RegionPass { +protected: + VecDirection Direction = VecDirection::BottomUp; + /// Set to true whenever the pass emits vector code in the current region. bool Change = false; /// The original instructions that are potentially dead after vectorization. DenseSet<Instruction *> DeadInstrCandidates; @@ -61,6 +67,10 @@ class LLVM_ABI BottomUpVec final : public RegionPass { /// for loads/stores) so that they can be cleaned up later. void collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl); + StringRef vecDirectionToStr() { + return Direction == VecDirection::TopDown ? "TopDownVec" : "BottomUpVec"; + } + /// Helper class describing how(if) to vectorize the code. class ActionsVector { private: @@ -84,8 +94,11 @@ class LLVM_ABI BottomUpVec final : public RegionPass { /// vectorize in vectorizeRec(). unsigned DebugBndlCnt = 0; - /// Recursively try to vectorize \p Bndl and its operands. This populates the - /// `Actions` vector. + explicit BottomUpVec(StringRef Name, VecDirection Dir) + : RegionPass(Name), Direction(Dir) {} + + /// Recursively try to vectorize \p Bndl. For bottom-up vectorization \p + /// UserBndl tracks the bundle of users that led to this recursion. Action *vectorizeRec(ArrayRef<Value *> Bndl, ArrayRef<Value *> UserBndl, unsigned Depth, LegalityAnalysis &Legality); /// If the values in \p Bndl have external users, then emit unpacks and @@ -104,6 +117,13 @@ class LLVM_ABI BottomUpVec final : public RegionPass { bool runOnRegion(Region &Rgn, const Analyses &A) final; }; +/// Top-down vectorizer Region pass. It expects a "seed slice" in the Region's +/// Aux vector and walks down the def-use chain from the seed instructions. +class LLVM_ABI TopDownVec final : public BottomUpVec { +public: + TopDownVec() : BottomUpVec("top-down-vec", VecDirection::TopDown) {} +}; + } // namespace llvm::sandboxir #endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp index 6bf257fcf8b1d..ba3f4599f4129 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp @@ -13,6 +13,7 @@ #include "llvm/SandboxIR/Module.h" #include "llvm/SandboxIR/Region.h" #include "llvm/SandboxIR/Utils.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/Debug.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h" @@ -34,6 +35,7 @@ static cl::opt<unsigned long> static constexpr unsigned long StopBundleDisabled = std::numeric_limits<unsigned long>::max(); + static cl::opt<unsigned long> StopBundle("sbvec-stop-bndl", cl::init(StopBundleDisabled), cl::Hidden, cl::desc("Vectorize up to this many bundles.")); @@ -278,6 +280,58 @@ void BottomUpVec::collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl) { } } +/// From a user \p U0 of lane 0 (\p V0), try to form a bundle of matching users +/// for all lanes in \p Bndl. Used by the top-down vectorizer only. Returns an +/// empty vector if no complete bundle can be formed. +static SmallVector<Value *, 4> getNextUserBundle(ArrayRef<Value *> Bndl, + User *U0, Value *V0, + InstrMaps &IMaps) { + auto *UI0 = dyn_cast<Instruction>(U0); + if (!UI0 || IMaps.isVectorized(UI0)) + return {}; + + // Find the operand index at which U0 uses lane 0. + unsigned OpIdx = UI0->getNumOperands(); + for (unsigned Idx : seq<unsigned>(UI0->getNumOperands())) { + if (UI0->getOperand(Idx) == V0) { + OpIdx = Idx; + break; + } + } + if (OpIdx == UI0->getNumOperands()) + return {}; + + // Find a distinct matching user for each of the remaining lanes. + SmallVector<Value *, 4> NextUserBndl; + NextUserBndl.push_back(UI0); + SmallPtrSet<Instruction *, 4> Claimed; + Claimed.insert(UI0); + for (Value *V : drop_begin(Bndl)) { + Instruction *Match = nullptr; + for (User *U : V->users()) { + auto *UI = dyn_cast<Instruction>(U); + if (!UI || IMaps.isVectorized(UI) || Claimed.contains(UI)) + continue; + if (UI->getOpcode() != UI0->getOpcode() || + UI->getType() != UI0->getType()) + continue; + // The whole bundle must live in the same block. + if (UI->getParent() != UI0->getParent()) + continue; + // The user must consume this lane at the same operand index. + if (OpIdx >= UI->getNumOperands() || UI->getOperand(OpIdx) != V) + continue; + Match = UI; + break; + } + if (!Match) + return {}; + Claimed.insert(Match); + NextUserBndl.push_back(Match); + } + return NextUserBndl; +} + Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, ArrayRef<Value *> UserBndl, unsigned Depth, LegalityAnalysis &Legality) { @@ -285,9 +339,55 @@ Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, DebugBndlCnt++ >= StopBundle && StopBundle != StopBundleDisabled; LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "canVectorize() Bundle:\n"; VecUtils::dump(Bndl)); - const auto &LegalityRes = StopForDebug ? Legality.getForcedPackForDebugging() - : Legality.canVectorize(Bndl); + const auto &LegalityRes = + StopForDebug ? Legality.getForcedPackForDebugging() + : Legality.canVectorize(Bndl, + /*SkipScheduling=*/Direction == + VecDirection::TopDown); LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Legality: " << LegalityRes << "\n"); + + if (Direction == VecDirection::TopDown) { + auto ActionPtr = std::make_unique<Action>(&LegalityRes, Bndl, + ArrayRef<Value *>(), Depth); + Action *Action = ActionPtr.get(); + if (LegalityRes.getSubclassID() == LegalityResultID::Widen) + IMaps->registerVector(Bndl, Action); + + // Pre-order push so defs are before uses. + Actions.push_back(std::move(ActionPtr)); + switch (LegalityRes.getSubclassID()) { + case LegalityResultID::Widen: { + // Walk down the def-use chain. Each lane in \p Bndl may feed several + // users, so we form every compatible user bundle and recurse into each + // one. A user bundle is compatible only if all of its users share the + // same opcode and type, live in the same block, are distinct and not + // already vectorized, and consume their corresponding element of \p Bndl + // at the same operand index, so that the widened vector lines up as a + // single vector operand. + // + // Recursing right after forming each bundle marks its instructions as + // vectorized (pre-order registration), which prevents sibling bundles + // from claiming the same instruction and guarantees termination. + Value *V0 = Bndl[0]; + for (User *U0 : V0->users()) { + SmallVector<Value *, 4> NextUserBndl = + getNextUserBundle(Bndl, U0, V0, *IMaps); + if (NextUserBndl.size() == Bndl.size()) + vectorizeRec(NextUserBndl, Bndl, Depth + 1, Legality); + } + break; + } + case LegalityResultID::DiamondReuse: + case LegalityResultID::DiamondReuseMultiInput: + case LegalityResultID::DiamondReuseWithShuffle: + case LegalityResultID::Pack: + llvm_unreachable("Not implemented."); + } + + return Action; + } + + // Bottom up direction auto ActionPtr = std::make_unique<Action>(&LegalityRes, Bndl, UserBndl, Depth); SmallVector<Action *> Operands; @@ -362,13 +462,27 @@ void BottomUpVec::emitUnpacksForExternalUses(const ArrayRef<Value *> Bndl, } for (auto [Lane, Elm] : VecUtils::enumerateLanes(Bndl)) { + // Collect the distinct external users first. We can't redirect uses while + // iterating Elm's use list, as that would invalidate the iterator. + SmallVector<User *, 4> ExternalUsers; + SmallPtrSet<User *, 4> Seen; for (User *U : Elm->users()) { - // Skip users that we just vectorized. + // Skip users that we just vectorized. Note: we must only redirect the + // external (non-vectorized) uses to an unpack and leave the vectorized + // users untouched. A blanket replaceAllUsesWith() would also rewrite the + // operands of users we are going to vectorize but have not emitted yet + // (in the top-down direction a user bundle is emitted after its operand + // bundle), which would corrupt those operands. if (IMaps->isVectorized(U)) continue; - auto *LastUnpackV = VecUtils::unpack(Vec, Elm->getType(), Lane, WhereIt); - Elm->replaceAllUsesWith(LastUnpackV); + if (Seen.insert(U).second) + ExternalUsers.push_back(U); } + if (ExternalUsers.empty()) + continue; + auto *UnpackV = VecUtils::unpack(Vec, Elm->getType(), Lane, WhereIt); + for (User *U : ExternalUsers) + U->replaceUsesOfWith(Elm, UnpackV); } } @@ -387,22 +501,44 @@ Value *BottomUpVec::emitVectors() { case LegalityResultID::Widen: { auto *I = cast<Instruction>(Bndl[0]); SmallVector<Value *, 2> VecOperands; - switch (I->getOpcode()) { - case Instruction::Opcode::Load: - VecOperands.push_back(cast<LoadInst>(I)->getPointerOperand()); - break; - case Instruction::Opcode::Store: { - VecOperands.push_back(ActionPtr->Operands[0]->Vec); - VecOperands.push_back(cast<StoreInst>(I)->getPointerOperand()); - break; - } - default: - // Visit all operands. - for (Action *OpA : ActionPtr->Operands) { - auto *VecOp = OpA->Vec; - VecOperands.push_back(VecOp); + if (Direction == VecDirection::BottomUp) { + switch (I->getOpcode()) { + case Instruction::Opcode::Load: + VecOperands.push_back(cast<LoadInst>(I)->getPointerOperand()); + break; + case Instruction::Opcode::Store: + VecOperands.push_back(ActionPtr->Operands[0]->Vec); + VecOperands.push_back(cast<StoreInst>(I)->getPointerOperand()); + break; + default: + for (Action *OpA : ActionPtr->Operands) + VecOperands.push_back(OpA->Vec); + break; + } + } else { + switch (I->getOpcode()) { + case Instruction::Opcode::Load: + VecOperands.push_back(cast<LoadInst>(I)->getPointerOperand()); + break; + case Instruction::Opcode::Store: { + auto OpBndl = getOperand(Bndl, 0); + if (Action *OpA = IMaps->getVectorForOrig(OpBndl[0])) + VecOperands.push_back(OpA->Vec); + else + VecOperands.push_back(createPack(OpBndl, UserBB)); + VecOperands.push_back(cast<StoreInst>(I)->getPointerOperand()); + break; + } + default: + for (unsigned OpIdx = 0; OpIdx < I->getNumOperands(); ++OpIdx) { + SmallVector<Value *, 4> OpBndl = getOperand(Bndl, OpIdx); + if (Action *OpA = IMaps->getVectorForOrig(OpBndl[0])) + VecOperands.push_back(OpA->Vec); + else + VecOperands.push_back(createPack(OpBndl, UserBB)); + } + break; } - break; } NewVec = createVectorInstr(ActionPtr->Bndl, VecOperands); // Collect any potentially dead scalar instructions, including the @@ -526,7 +662,8 @@ bool BottomUpVec::tryVectorize(ArrayRef<Value *> Bndl, Actions.clear(); DebugBndlCnt = 0; vectorizeRec(Bndl, {}, /*Depth=*/0, Legality); - LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "BottomUpVec: Vectorization Actions:\n"; + LLVM_DEBUG(dbgs() << DEBUG_PREFIX << vecDirectionToStr() + << ": Vectorization Actions:\n"; Actions.dump()); emitVectors(); tryEraseDeadInstrs(); diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def index 10ba595910ee9..40d03c3886c0b 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def @@ -26,6 +26,7 @@ REGION_PASS("tr-accept", ::llvm::sandboxir::TransactionAlwaysAccept) REGION_PASS("tr-revert", ::llvm::sandboxir::TransactionAlwaysRevert) REGION_PASS("tr-accept-or-revert", ::llvm::sandboxir::TransactionAcceptOrRevert) REGION_PASS("bottom-up-vec", ::llvm::sandboxir::BottomUpVec) +REGION_PASS("top-down-vec", ::llvm::sandboxir::TopDownVec) REGION_PASS("load-store-vec", ::llvm::sandboxir::LoadStoreVec) #undef REGION_PASS diff --git a/llvm/test/Transforms/SandboxVectorizer/external_uses.ll b/llvm/test/Transforms/SandboxVectorizer/external_uses.ll index 593965ab01680..0bd6e9eebe5af 100644 --- a/llvm/test/Transforms/SandboxVectorizer/external_uses.ll +++ b/llvm/test/Transforms/SandboxVectorizer/external_uses.ll @@ -1,5 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6 -; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-collect-seeds=loads -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN ; Checks the handling of users outside the vectorized graph. @@ -13,6 +14,16 @@ define void @external_users(ptr %ptr) { ; CHECK-NEXT: store <2 x float> [[VEC]], ptr [[PTR0]], align 4, !sandboxvec [[META0]] ; CHECK-NEXT: [[USER:%.*]] = fneg float [[SUB0]] ; CHECK-NEXT: ret void +; +; TOPDOWN-LABEL: define void @external_users( +; TOPDOWN-SAME: ptr [[PTR:%.*]]) { +; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; TOPDOWN-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META0:![0-9]+]] +; TOPDOWN-NEXT: [[VEC:%.*]] = fsub <2 x float> [[VECL]], zeroinitializer, !sandboxvec [[META0]] +; TOPDOWN-NEXT: [[SUB0:%.*]] = extractelement <2 x float> [[VEC]], i32 0, !sandboxvec [[META0]] +; TOPDOWN-NEXT: store <2 x float> [[VEC]], ptr [[PTR0]], align 4, !sandboxvec [[META0]] +; TOPDOWN-NEXT: [[USER:%.*]] = fneg float [[SUB0]] +; TOPDOWN-NEXT: ret void ; %ptr0 = getelementptr float, ptr %ptr, i32 0 %ptr1 = getelementptr float, ptr %ptr, i32 1 @@ -35,6 +46,17 @@ define void @external_user_of_constant(ptr %ptr, ptr %ptrX) { ; CHECK-NEXT: store <2 x i32> zeroinitializer, ptr [[PTR0]], align 4, !sandboxvec [[META1:![0-9]+]] ; CHECK-NEXT: store i32 0, ptr [[PTRX]], align 4 ; CHECK-NEXT: ret void +; +; TOPDOWN-LABEL: define void @external_user_of_constant( +; TOPDOWN-SAME: ptr [[PTR:%.*]], ptr [[PTRX:%.*]]) { +; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr float, ptr [[PTR]], i32 1 +; TOPDOWN-NEXT: [[ZEXT0:%.*]] = zext i16 0 to i32 +; TOPDOWN-NEXT: [[ZEXT1:%.*]] = zext i16 0 to i32 +; TOPDOWN-NEXT: store i32 [[ZEXT0]], ptr [[PTR0]], align 4 +; TOPDOWN-NEXT: store i32 [[ZEXT1]], ptr [[PTR1]], align 4 +; TOPDOWN-NEXT: store i32 [[ZEXT0]], ptr [[PTRX]], align 4 +; TOPDOWN-NEXT: ret void ; %ptr0 = getelementptr float, ptr %ptr, i32 0 %ptr1 = getelementptr float, ptr %ptr, i32 1 @@ -57,6 +79,20 @@ define void @vector_external_users(ptr %ptr) { ; CHECK-NEXT: store <3 x float> [[VEC]], ptr [[PTR0]], align 4, !sandboxvec [[META2]] ; CHECK-NEXT: [[USER:%.*]] = fneg <2 x float> [[UNPACKINS2]] ; CHECK-NEXT: ret void +; +; TOPDOWN-LABEL: define void @vector_external_users( +; TOPDOWN-SAME: ptr [[PTR:%.*]]) { +; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr float, ptr [[PTR]], i32 1 +; TOPDOWN-NEXT: [[VECL:%.*]] = load <3 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META1:![0-9]+]] +; TOPDOWN-NEXT: [[LD0:%.*]] = extractelement <3 x float> [[VECL]], i32 0, !sandboxvec [[META1]] +; TOPDOWN-NEXT: [[LD1:%.*]] = shufflevector <3 x float> [[VECL]], <3 x float> poison, <2 x i32> <i32 1, i32 2>, !sandboxvec [[META1]] +; TOPDOWN-NEXT: [[SUB0:%.*]] = fsub float [[LD0]], 0.000000e+00 +; TOPDOWN-NEXT: [[SUB1:%.*]] = fsub <2 x float> [[LD1]], zeroinitializer +; TOPDOWN-NEXT: store float [[SUB0]], ptr [[PTR0]], align 4 +; TOPDOWN-NEXT: store <2 x float> [[SUB1]], ptr [[PTR1]], align 8 +; TOPDOWN-NEXT: [[USER:%.*]] = fneg <2 x float> [[SUB1]] +; TOPDOWN-NEXT: ret void ; %ptr0 = getelementptr float, ptr %ptr, i32 0 %ptr1 = getelementptr float, ptr %ptr, i32 1 @@ -80,6 +116,16 @@ define void @vector_external_users_lane_and_index_differ(ptr %ptr) { ; CHECK-NEXT: store <4 x float> [[VEC]], ptr [[PTR0]], align 8, !sandboxvec [[META3]] ; CHECK-NEXT: [[USER:%.*]] = fneg <2 x float> [[UNPACK]] ; CHECK-NEXT: ret void +; +; TOPDOWN-LABEL: define void @vector_external_users_lane_and_index_differ( +; TOPDOWN-SAME: ptr [[PTR:%.*]]) { +; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr <2 x float>, ptr [[PTR]], i32 0 +; TOPDOWN-NEXT: [[VECL:%.*]] = load <4 x float>, ptr [[PTR0]], align 8, !sandboxvec [[META2:![0-9]+]] +; TOPDOWN-NEXT: [[VEC:%.*]] = fsub <4 x float> [[VECL]], zeroinitializer, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[SUB1:%.*]] = shufflevector <4 x float> [[VEC]], <4 x float> poison, <2 x i32> <i32 2, i32 3>, !sandboxvec [[META2]] +; TOPDOWN-NEXT: store <4 x float> [[VEC]], ptr [[PTR0]], align 8, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[USER:%.*]] = fneg <2 x float> [[SUB1]] +; TOPDOWN-NEXT: ret void ; %ptr0 = getelementptr <2 x float>, ptr %ptr, i32 0 %ptr1 = getelementptr <2 x float>, ptr %ptr, i32 1 @@ -99,3 +145,7 @@ define void @vector_external_users_lane_and_index_differ(ptr %ptr) { ; CHECK: [[META2]] = distinct !{!"sandboxregion"} ; CHECK: [[META3]] = distinct !{!"sandboxregion"} ;. +; TOPDOWN: [[META0]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META1]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META2]] = distinct !{!"sandboxregion"} +;. diff --git a/llvm/test/Transforms/SandboxVectorizer/pack.ll b/llvm/test/Transforms/SandboxVectorizer/pack.ll index 743d705fd48ff..6a91f3cdb5d24 100644 --- a/llvm/test/Transforms/SandboxVectorizer/pack.ll +++ b/llvm/test/Transforms/SandboxVectorizer/pack.ll @@ -1,5 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 -; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN define void @pack_constants(ptr %ptr) { ; CHECK-LABEL: define void @pack_constants( @@ -7,6 +8,12 @@ define void @pack_constants(ptr %ptr) { ; CHECK-NEXT: [[PTR0:%.*]] = getelementptr i8, ptr [[PTR]], i32 0 ; CHECK-NEXT: store <2 x i8> <i8 0, i8 1>, ptr [[PTR0]], align 1, !sandboxvec [[META0:![0-9]+]] ; CHECK-NEXT: ret void +; +; TOPDOWN-LABEL: define void @pack_constants( +; TOPDOWN-SAME: ptr [[PTR:%.*]]) { +; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr i8, ptr [[PTR]], i32 0 +; TOPDOWN-NEXT: store <2 x i8> <i8 0, i8 1>, ptr [[PTR0]], align 1, !sandboxvec [[META0:![0-9]+]] +; TOPDOWN-NEXT: ret void ; %ptr0 = getelementptr i8, ptr %ptr, i32 0 %ptr1 = getelementptr i8, ptr %ptr, i32 1 @@ -27,14 +34,31 @@ define void @packPHIs(ptr %ptr) { ; CHECK-NEXT: [[PHI1:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] ; CHECK-NEXT: [[PHI2:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] ; CHECK-NEXT: [[PHI3:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] -; CHECK-NEXT: [[PACK:%.*]] = insertelement <2 x i8> poison, i8 [[PHI0]], i32 0, !sandboxvec [[META1:![0-9]+]] -; CHECK-NEXT: [[PACK1:%.*]] = insertelement <2 x i8> [[PACK]], i8 [[PHI1]], i32 1, !sandboxvec [[META1]] +; CHECK-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[PHI0]], i32 0, !sandboxvec [[META1:![0-9]+]] +; CHECK-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[PHI1]], i32 1, !sandboxvec [[META1]] ; CHECK-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 -; CHECK-NEXT: store <2 x i8> [[PACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META1]] +; CHECK-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META1]] ; CHECK-NEXT: br label %[[LOOP]] ; CHECK: [[EXIT:.*:]] ; CHECK-NEXT: ret void ; +; TOPDOWN-LABEL: define void @packPHIs( +; TOPDOWN-SAME: ptr [[PTR:%.*]]) { +; TOPDOWN-NEXT: [[ENTRY:.*]]: +; TOPDOWN-NEXT: br label %[[LOOP:.*]] +; TOPDOWN: [[LOOP]]: +; TOPDOWN-NEXT: [[PHI0:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[PHI1:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[PHI2:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[PHI3:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[PHI0]], i32 0, !sandboxvec [[META1:![0-9]+]] +; TOPDOWN-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[PHI1]], i32 1, !sandboxvec [[META1]] +; TOPDOWN-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 +; TOPDOWN-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META1]] +; TOPDOWN-NEXT: br label %[[LOOP]] +; TOPDOWN: [[EXIT:.*:]] +; TOPDOWN-NEXT: ret void +; entry: br label %loop @@ -63,14 +87,31 @@ define void @packFromOtherBB(ptr %ptr, i8 %val) { ; CHECK: [[LOOP]]: ; CHECK-NEXT: [[PHI0:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] ; CHECK-NEXT: [[PHI1:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] -; CHECK-NEXT: [[PACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META2:![0-9]+]] -; CHECK-NEXT: [[PACK1:%.*]] = insertelement <2 x i8> [[PACK]], i8 [[MUL1]], i32 1, !sandboxvec [[META2]] +; CHECK-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META2:![0-9]+]] +; CHECK-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[MUL1]], i32 1, !sandboxvec [[META2]] ; CHECK-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 -; CHECK-NEXT: store <2 x i8> [[PACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META2]] +; CHECK-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META2]] ; CHECK-NEXT: br label %[[LOOP]] ; CHECK: [[EXIT:.*:]] ; CHECK-NEXT: ret void ; +; TOPDOWN-LABEL: define void @packFromOtherBB( +; TOPDOWN-SAME: ptr [[PTR:%.*]], i8 [[VAL:%.*]]) { +; TOPDOWN-NEXT: [[ENTRY:.*]]: +; TOPDOWN-NEXT: [[ADD0:%.*]] = add i8 [[VAL]], 0 +; TOPDOWN-NEXT: [[MUL1:%.*]] = mul i8 [[VAL]], 1 +; TOPDOWN-NEXT: br label %[[LOOP:.*]] +; TOPDOWN: [[LOOP]]: +; TOPDOWN-NEXT: [[PHI0:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[PHI1:%.*]] = phi i8 [ 0, %[[ENTRY]] ], [ 1, %[[LOOP]] ] +; TOPDOWN-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META2:![0-9]+]] +; TOPDOWN-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[MUL1]], i32 1, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 +; TOPDOWN-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META2]] +; TOPDOWN-NEXT: br label %[[LOOP]] +; TOPDOWN: [[EXIT:.*:]] +; TOPDOWN-NEXT: ret void +; entry: %add0 = add i8 %val, 0 %mul1 = mul i8 %val, 1 @@ -97,12 +138,25 @@ define void @packFromDiffBBs(ptr %ptr, i8 %v) { ; CHECK-NEXT: br label %[[BB:.*]] ; CHECK: [[BB]]: ; CHECK-NEXT: [[ADD1:%.*]] = add i8 [[V]], 2 -; CHECK-NEXT: [[PACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META3:![0-9]+]] -; CHECK-NEXT: [[PACK1:%.*]] = insertelement <2 x i8> [[PACK]], i8 [[ADD1]], i32 1, !sandboxvec [[META3]] +; CHECK-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META3:![0-9]+]] +; CHECK-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[ADD1]], i32 1, !sandboxvec [[META3]] ; CHECK-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 -; CHECK-NEXT: store <2 x i8> [[PACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META3]] +; CHECK-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META3]] ; CHECK-NEXT: ret void ; +; TOPDOWN-LABEL: define void @packFromDiffBBs( +; TOPDOWN-SAME: ptr [[PTR:%.*]], i8 [[V:%.*]]) { +; TOPDOWN-NEXT: [[ENTRY:.*:]] +; TOPDOWN-NEXT: [[ADD0:%.*]] = add i8 [[V]], 1 +; TOPDOWN-NEXT: br label %[[BB:.*]] +; TOPDOWN: [[BB]]: +; TOPDOWN-NEXT: [[ADD1:%.*]] = add i8 [[V]], 2 +; TOPDOWN-NEXT: [[VPACK:%.*]] = insertelement <2 x i8> poison, i8 [[ADD0]], i32 0, !sandboxvec [[META3:![0-9]+]] +; TOPDOWN-NEXT: [[VPACK1:%.*]] = insertelement <2 x i8> [[VPACK]], i8 [[ADD1]], i32 1, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[GEP0:%.*]] = getelementptr i8, ptr [[PTR]], i64 0 +; TOPDOWN-NEXT: store <2 x i8> [[VPACK1]], ptr [[GEP0]], align 1, !sandboxvec [[META3]] +; TOPDOWN-NEXT: ret void +; entry: %add0 = add i8 %v, 1 br label %bb @@ -121,3 +175,8 @@ bb: ; CHECK: [[META2]] = distinct !{!"sandboxregion"} ; CHECK: [[META3]] = distinct !{!"sandboxregion"} ;. +; TOPDOWN: [[META0]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META1]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META2]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META3]] = distinct !{!"sandboxregion"} +;. diff --git a/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll new file mode 100644 index 0000000000000..1f2b697c3b5b0 --- /dev/null +++ b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll @@ -0,0 +1,304 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 \ +; RUN: -sbvec-collect-seeds=loads -sbvec-always-verify \ +; RUN: -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" \ +; RUN: %s -S | FileCheck %s + +; Tests: successful bundle match (baseline) and !IMaps->isVectorized(UI0) on +; the outer loop's second use edge (%ld0 used twice by the same fadd). +define void @load_fadd_store(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @load_fadd_store( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META0:![0-9]+]] +; CHECK-NEXT: [[VEC:%.*]] = fadd <2 x float> [[VECL]], [[VECL]], !sandboxvec [[META0]] +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: store <2 x float> [[VEC]], ptr [[PTR2_0]], align 4, !sandboxvec [[META0]] +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ld0 = load float, ptr %ptr0 + %ld1 = load float, ptr %ptr1 + + %fadd0 = fadd float %ld0, %ld0 + %fadd1 = fadd float %ld1, %ld1 + + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + store float %fadd0, ptr %ptr2_0 + store float %fadd1, ptr %ptr2_1 + ret void +} + +define void @load_chain_store(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @load_chain_store( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META1:![0-9]+]] +; CHECK-NEXT: [[VEC:%.*]] = fmul <2 x float> [[VECL]], splat (float 3.000000e+00), !sandboxvec [[META1]] +; CHECK-NEXT: [[VEC1:%.*]] = fadd <2 x float> [[VEC]], splat (float 2.000000e+00), !sandboxvec [[META1]] +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: store <2 x float> [[VEC1]], ptr [[PTR2_0]], align 4, !sandboxvec [[META1]] +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ld0 = load float, ptr %ptr0 + %ld1 = load float, ptr %ptr1 + + %fmul0 = fmul float %ld0, 3.0 + %fmul1 = fmul float %ld1, 3.0 + + %fadd0 = fadd float %fmul0, 2.0 + %fadd1 = fadd float %fmul1, 2.0 + + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + store float %fadd0, ptr %ptr2_0 + store float %fadd1, ptr %ptr2_1 + ret void +} + +define float @load_fadd_external_use(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define float @load_fadd_external_use( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META2:![0-9]+]] +; CHECK-NEXT: [[VEC:%.*]] = fadd <2 x float> [[VECL]], [[VECL]], !sandboxvec [[META2]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VEC]], i32 0, !sandboxvec [[META2]] +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: store <2 x float> [[VEC]], ptr [[PTR2_0]], align 4, !sandboxvec [[META2]] +; CHECK-NEXT: ret float [[UNPACK]] +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ld0 = load float, ptr %ptr0 + %ld1 = load float, ptr %ptr1 + + %fadd0 = fadd float %ld0, %ld0 + %fadd1 = fadd float %ld1, %ld1 + + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + store float %fadd0, ptr %ptr2_0 + store float %fadd1, ptr %ptr2_1 + + ret float %fadd0 +} + +; Both lanes feed the *same* user instruction (once per operand). The user +; bundle must not be formed out of duplicate instructions, so the fadd stays +; scalar while the loads still widen. +define float @single_user_no_duplicate(ptr %ptr) { +; CHECK-LABEL: define float @single_user_no_duplicate( +; CHECK-SAME: ptr [[PTR:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META3:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META3]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META3]] +; CHECK-NEXT: [[FADD:%.*]] = fadd float [[UNPACK]], [[UNPACK1]] +; CHECK-NEXT: ret float [[FADD]] +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ld0 = load float, ptr %ptr0 + %ld1 = load float, ptr %ptr1 + + %fadd = fadd float %ld0, %ld1 + ret float %fadd +} + +; The candidate users live in different blocks from each other, so they must +; not be bundled together. +define void @users_in_different_blocks(ptr %ptr, ptr %ptr2, i1 %c) { +; CHECK-LABEL: define void @users_in_different_blocks( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]], i1 [[C:%.*]]) { +; CHECK-NEXT: [[ENTRY:.*:]] +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META4:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META4]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META4]] +; CHECK-NEXT: br i1 [[C]], label %[[BB0:.*]], label %[[BB1:.*]] +; CHECK: [[BB0]]: +; CHECK-NEXT: [[FADD0:%.*]] = fadd float [[UNPACK]], [[UNPACK]] +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: store float [[FADD0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: ret void +; CHECK: [[BB1]]: +; CHECK-NEXT: [[FADD1:%.*]] = fadd float [[UNPACK1]], [[UNPACK1]] +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr float, ptr [[PTR2]], i32 1 +; CHECK-NEXT: store float [[FADD1]], ptr [[PTR2_1]], align 4 +; CHECK-NEXT: ret void +; +entry: + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ld0 = load float, ptr %ptr0 + %ld1 = load float, ptr %ptr1 + br i1 %c, label %if.then, label %if.else + +if.then: + %fadd0 = fadd float %ld0, %ld0 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + store float %fadd0, ptr %ptr2_0 + ret void + +if.else: + %fadd1 = fadd float %ld1, %ld1 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + store float %fadd1, ptr %ptr2_1 + ret void +} + +; Lane 0 feeds fadd, lane 1 feeds fmul — opcode mismatch rejects the bundle. +define void @user_opcode_mismatch(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @user_opcode_mismatch( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr float, ptr [[PTR2]], i32 1 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META5:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META5]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META5]] +; CHECK-NEXT: [[FADD0:%.*]] = fadd float [[UNPACK]], [[UNPACK]] +; CHECK-NEXT: [[FMUL1:%.*]] = fmul float [[UNPACK1]], [[UNPACK1]] +; CHECK-NEXT: store float [[FADD0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store float [[FMUL1]], ptr [[PTR2_1]], align 4 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + %fadd0 = fadd float %ld0, %ld0 + %fmul1 = fmul float %ld1, %ld1 + + store float %fadd0, ptr %ptr2_0, align 4 + store float %fmul1, ptr %ptr2_1, align 4 + ret void +} + +; Lane 0's user is fadd float, lane 1's user is fadd double — type mismatch. +define void @user_type_mismatch(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @user_type_mismatch( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr double, ptr [[PTR2]], i32 1 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META6:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META6]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META6]] +; CHECK-NEXT: [[FADD0:%.*]] = fadd float [[UNPACK]], [[UNPACK]] +; CHECK-NEXT: [[EXT1:%.*]] = fpext float [[UNPACK1]] to double +; CHECK-NEXT: [[FADD1:%.*]] = fadd double [[EXT1]], [[EXT1]] +; CHECK-NEXT: store float [[FADD0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store double [[FADD1]], ptr [[PTR2_1]], align 8 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr double, ptr %ptr2, i32 1 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + %fadd0 = fadd float %ld0, %ld0 + %ext1 = fpext float %ld1 to double + %fadd1 = fadd double %ext1, %ext1 + + store float %fadd0, ptr %ptr2_0, align 4 + store double %fadd1, ptr %ptr2_1, align 8 + ret void +} + +; Lane 0 uses ld0 at operand 0; lane 1 uses ld1 at operand 1 (fsub is not +; commutative). Operand-index mismatch rejects the bundle. +define void @user_operand_index_mismatch(ptr %ptr, ptr %ptr2, float %x) { +; CHECK-LABEL: define void @user_operand_index_mismatch( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]], float [[X:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr float, ptr [[PTR2]], i32 1 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META7:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META7]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META7]] +; CHECK-NEXT: [[FSUB0:%.*]] = fsub float [[UNPACK]], [[X]] +; CHECK-NEXT: [[FSUB1:%.*]] = fsub float [[X]], [[UNPACK1]] +; CHECK-NEXT: store float [[FSUB0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store float [[FSUB1]], ptr [[PTR2_1]], align 4 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + %fsub0 = fsub float %ld0, %x + %fsub1 = fsub float %x, %ld1 + + store float %fsub0, ptr %ptr2_0, align 4 + store float %fsub1, ptr %ptr2_1, align 4 + ret void +} + +; ld0 has two fadd users; the first bundle {fadd0,fadd1} vectorizes fadd1. +; When matching the second bundle, fadd1 is skipped (already vectorized) and +; fadd1b is chosen instead. +define void @user_already_vectorized(ptr %ptr, ptr %ptr2, float %a, float %b) { +; CHECK-LABEL: define void @user_already_vectorized( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]], float [[A:%.*]], float [[B:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PACK2:%.*]] = insertelement <2 x float> poison, float [[A]], i32 0, !sandboxvec [[META8:![0-9]+]] +; CHECK-NEXT: [[PACK3:%.*]] = insertelement <2 x float> [[PACK2]], float [[A]], i32 1, !sandboxvec [[META8]] +; CHECK-NEXT: [[PACK:%.*]] = insertelement <2 x float> poison, float [[B]], i32 0, !sandboxvec [[META8]] +; CHECK-NEXT: [[PACK1:%.*]] = insertelement <2 x float> [[PACK]], float [[B]], i32 1, !sandboxvec [[META8]] +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_2:%.*]] = getelementptr float, ptr [[PTR2]], i32 2 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META8]] +; CHECK-NEXT: [[VEC4:%.*]] = fadd <2 x float> [[VECL]], [[PACK3]], !sandboxvec [[META8]] +; CHECK-NEXT: [[VEC:%.*]] = fadd <2 x float> [[VECL]], [[PACK1]], !sandboxvec [[META8]] +; CHECK-NEXT: store <2 x float> [[VEC4]], ptr [[PTR2_0]], align 4, !sandboxvec [[META8]] +; CHECK-NEXT: store <2 x float> [[VEC]], ptr [[PTR2_2]], align 4, !sandboxvec [[META8]] +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + %ptr2_2 = getelementptr float, ptr %ptr2, i32 2 + %ptr2_3 = getelementptr float, ptr %ptr2, i32 3 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + %fadd0 = fadd float %ld0, %a + %fadd0b = fadd float %ld0, %b + %fadd1 = fadd float %ld1, %a + %fadd1b = fadd float %ld1, %b + + store float %fadd0, ptr %ptr2_0, align 4 + store float %fadd1, ptr %ptr2_1, align 4 + store float %fadd0b, ptr %ptr2_2, align 4 + store float %fadd1b, ptr %ptr2_3, align 4 + ret void +} +;. +; CHECK: [[META0]] = distinct !{!"sandboxregion"} +; CHECK: [[META1]] = distinct !{!"sandboxregion"} +; CHECK: [[META2]] = distinct !{!"sandboxregion"} +; CHECK: [[META3]] = distinct !{!"sandboxregion"} +; CHECK: [[META4]] = distinct !{!"sandboxregion"} +; CHECK: [[META5]] = distinct !{!"sandboxregion"} +; CHECK: [[META6]] = distinct !{!"sandboxregion"} +; CHECK: [[META7]] = distinct !{!"sandboxregion"} +; CHECK: [[META8]] = distinct !{!"sandboxregion"} +;. >From c027602603bf2ea579f93b9bbba69796c01f01b1 Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Tue, 30 Jun 2026 14:52:36 -0400 Subject: [PATCH 3/6] [SandboxVec] Vectorize in the same direction as the scheduler direction --- .../Vectorize/SandboxVectorizer/Legality.h | 2 ++ .../SandboxVectorizer/Passes/BottomUpVec.h | 22 ++++++++--------- .../Vectorize/SandboxVectorizer/Scheduler.h | 1 + .../SandboxVectorizer/Passes/BottomUpVec.cpp | 24 +++++++++++-------- 4 files changed, 27 insertions(+), 22 deletions(-) diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h index b1fa6ed7742e8..27a93cedd78c0 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h @@ -337,6 +337,8 @@ class LegalityAnalysis { LegalityAnalysis(AAResults &AA, ScalarEvolution &SE, const DataLayout &DL, Context &Ctx, InstrMaps &IMaps) : Sched(AA, Ctx), SE(SE), DL(DL), IMaps(IMaps) {} + SchedDirection getDirection() const { return Sched.getDirection(); } + void setDirection(SchedDirection NewDir) { Sched.setDirection(NewDir); } /// A LegalityResult factory. template <typename ResultT, typename... ArgsT> ResultT &createLegalityResult(ArgsT &&...Args) { diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h index 680e04b5dc2ee..81a934df90048 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h @@ -23,8 +23,6 @@ namespace llvm::sandboxir { -enum class VecDirection { TopDown, BottomUp }; - /// This is a simple bottom-up vectorizer Region pass. /// It expects a "seed slice" as an input in the Region's Aux vector. /// The "seed slice" is a vector of instructions that can be used as a starting @@ -37,7 +35,9 @@ enum class VecDirection { TopDown, BottomUp }; /// transaction, depending on the cost. class LLVM_ABI BottomUpVec : public RegionPass { protected: - VecDirection Direction = VecDirection::BottomUp; + virtual SchedDirection getSchedDirection() const { + return SchedDirection::BottomUp; + } /// Set to true whenever the pass emits vector code in the current region. bool Change = false; /// The original instructions that are potentially dead after vectorization. @@ -67,10 +67,6 @@ class LLVM_ABI BottomUpVec : public RegionPass { /// for loads/stores) so that they can be cleaned up later. void collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl); - StringRef vecDirectionToStr() { - return Direction == VecDirection::TopDown ? "TopDownVec" : "BottomUpVec"; - } - /// Helper class describing how(if) to vectorize the code. class ActionsVector { private: @@ -94,9 +90,6 @@ class LLVM_ABI BottomUpVec : public RegionPass { /// vectorize in vectorizeRec(). unsigned DebugBndlCnt = 0; - explicit BottomUpVec(StringRef Name, VecDirection Dir) - : RegionPass(Name), Direction(Dir) {} - /// Recursively try to vectorize \p Bndl. For bottom-up vectorization \p /// UserBndl tracks the bundle of users that led to this recursion. Action *vectorizeRec(ArrayRef<Value *> Bndl, ArrayRef<Value *> UserBndl, @@ -106,7 +99,7 @@ class LLVM_ABI BottomUpVec : public RegionPass { void emitUnpacksForExternalUses(const ArrayRef<Value *> Bndl, Value *Vec); /// Generate vector instructions based on `Actions` and return the last vector /// created. - Value *emitVectors(); + Value *emitVectors(LegalityAnalysis &Legality); /// Entry point for vectorization starting from \p Seeds. bool tryVectorize(ArrayRef<Value *> Seeds, LegalityAnalysis &Legality); @@ -120,8 +113,13 @@ class LLVM_ABI BottomUpVec : public RegionPass { /// Top-down vectorizer Region pass. It expects a "seed slice" in the Region's /// Aux vector and walks down the def-use chain from the seed instructions. class LLVM_ABI TopDownVec final : public BottomUpVec { +protected: + SchedDirection getSchedDirection() const override { + return SchedDirection::TopDown; + } + public: - TopDownVec() : BottomUpVec("top-down-vec", VecDirection::TopDown) {} + TopDownVec() : BottomUpVec("top-down-vec") {} }; } // namespace llvm::sandboxir diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h index 86ab5fb8b464b..ea36b030c83b1 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h @@ -240,6 +240,7 @@ class Scheduler { if (CreateInstrCB) Ctx.unregisterCreateInstrCallback(*CreateInstrCB); } + SchedDirection getDirection() const { return Dir; } void setDirection(SchedDirection NewDir) { assert(Bndls.empty() && DAG.empty() && ReadyList.empty() && !ScheduleTopItOpt && ScheduledBB == nullptr && diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp index ba3f4599f4129..819d3415632f2 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp @@ -15,6 +15,7 @@ #include "llvm/SandboxIR/Utils.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/Debug.h" +#include "llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h" namespace llvm { @@ -340,13 +341,14 @@ Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "canVectorize() Bundle:\n"; VecUtils::dump(Bndl)); const auto &LegalityRes = - StopForDebug ? Legality.getForcedPackForDebugging() - : Legality.canVectorize(Bndl, - /*SkipScheduling=*/Direction == - VecDirection::TopDown); + StopForDebug + ? Legality.getForcedPackForDebugging() + : Legality.canVectorize(Bndl, + /*SkipScheduling=*/Legality.getDirection() == + SchedDirection::TopDown); LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Legality: " << LegalityRes << "\n"); - if (Direction == VecDirection::TopDown) { + if (Legality.getDirection() == SchedDirection::TopDown) { auto ActionPtr = std::make_unique<Action>(&LegalityRes, Bndl, ArrayRef<Value *>(), Depth); Action *Action = ActionPtr.get(); @@ -486,7 +488,7 @@ void BottomUpVec::emitUnpacksForExternalUses(const ArrayRef<Value *> Bndl, } } -Value *BottomUpVec::emitVectors() { +Value *BottomUpVec::emitVectors(LegalityAnalysis &Legality) { Value *NewVec = nullptr; for (const auto &ActionPtr : Actions) { ArrayRef<Value *> Bndl = ActionPtr->Bndl; @@ -501,7 +503,7 @@ Value *BottomUpVec::emitVectors() { case LegalityResultID::Widen: { auto *I = cast<Instruction>(Bndl[0]); SmallVector<Value *, 2> VecOperands; - if (Direction == VecDirection::BottomUp) { + if (Legality.getDirection() == SchedDirection::BottomUp) { switch (I->getOpcode()) { case Instruction::Opcode::Load: VecOperands.push_back(cast<LoadInst>(I)->getPointerOperand()); @@ -662,10 +664,11 @@ bool BottomUpVec::tryVectorize(ArrayRef<Value *> Bndl, Actions.clear(); DebugBndlCnt = 0; vectorizeRec(Bndl, {}, /*Depth=*/0, Legality); - LLVM_DEBUG(dbgs() << DEBUG_PREFIX << vecDirectionToStr() - << ": Vectorization Actions:\n"; + LLVM_DEBUG(dbgs() << DEBUG_PREFIX + << schedDirectionToStr(Legality.getDirection()) + << "Vec: Vectorization Actions:\n"; Actions.dump()); - emitVectors(); + emitVectors(Legality); tryEraseDeadInstrs(); return Change; } @@ -678,6 +681,7 @@ bool BottomUpVec::runOnRegion(Region &Rgn, const Analyses &A) { LegalityAnalysis Legality(A.getAA(), A.getScalarEvolution(), F.getParent()->getDataLayout(), F.getContext(), *IMaps); + Legality.setDirection(getSchedDirection()); // TODO: Refactor to remove the unnecessary copy to SeedSliceVals. SmallVector<Value *> SeedSliceVals(SeedSlice.begin(), SeedSlice.end()); >From d98cf0b0021757cbd13d5d9a5eb4261647d51923 Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Thu, 2 Jul 2026 13:50:15 -0400 Subject: [PATCH 4/6] [SandboxVec] Use AuxArg to determine vectorizer direction --- .../SandboxVectorizer/Passes/BottomUpVec.h | 44 ++++++++-------- .../SandboxVectorizer/Passes/BottomUpVec.cpp | 3 +- .../SandboxVectorizer/Passes/PassRegistry.def | 1 - .../SandboxVectorizer/external_uses.ll | 52 +++++++++++++------ .../test/Transforms/SandboxVectorizer/pack.ll | 2 +- .../SandboxVectorizer/topdown_vec.ll | 2 +- 6 files changed, 62 insertions(+), 42 deletions(-) diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h index 81a934df90048..ae60666aa0df5 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.h @@ -6,8 +6,8 @@ // //===----------------------------------------------------------------------===// // -// A bottom-up vectorizer pass. TopDownVec reuses this implementation with a -// different traversal direction. +// A vectorizer pass that walks the def-use chain bottom-up or top-down, +// depending on the auxiliary pass argument. // #ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_PASSES_BOTTOMUPVEC_H @@ -17,13 +17,15 @@ #include "llvm/ADT/StringRef.h" #include "llvm/SandboxIR/Constant.h" #include "llvm/SandboxIR/Pass.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h" #include "llvm/Transforms/Vectorize/SandboxVectorizer/Legality.h" +#include "llvm/Transforms/Vectorize/SandboxVectorizer/Scheduler.h" namespace llvm::sandboxir { -/// This is a simple bottom-up vectorizer Region pass. +/// This is a simple vectorizer Region pass. /// It expects a "seed slice" as an input in the Region's Aux vector. /// The "seed slice" is a vector of instructions that can be used as a starting /// point for vectorization, like stores to consecutive memory addresses. @@ -33,13 +35,14 @@ namespace llvm::sandboxir { /// profitable or not. For now profitability is checked at the end of the region /// pass pipeline by a dedicated pass that accepts or rejects the IR /// transaction, depending on the cost. -class LLVM_ABI BottomUpVec : public RegionPass { -protected: - virtual SchedDirection getSchedDirection() const { - return SchedDirection::BottomUp; - } +class LLVM_ABI BottomUpVec final : public RegionPass { +private: /// Set to true whenever the pass emits vector code in the current region. bool Change = false; + static constexpr StringRef TopDownArgStr = "top-down"; + static constexpr StringRef BottomUpArgStr = "bottom-up"; + /// Direction for vectorization, defaults to bottom-up. + SchedDirection Dir = SchedDirection::BottomUp; /// The original instructions that are potentially dead after vectorization. DenseSet<Instruction *> DeadInstrCandidates; /// Maps scalars to vectors. @@ -105,21 +108,20 @@ class LLVM_ABI BottomUpVec : public RegionPass { public: BottomUpVec(StringRef AuxArg) : RegionPass("bottom-up-vec") { - assert(AuxArg.empty() && "This pass ignores aux arg!"); - } - bool runOnRegion(Region &Rgn, const Analyses &A) final; -}; - -/// Top-down vectorizer Region pass. It expects a "seed slice" in the Region's -/// Aux vector and walks down the def-use chain from the seed instructions. -class LLVM_ABI TopDownVec final : public BottomUpVec { -protected: - SchedDirection getSchedDirection() const override { - return SchedDirection::TopDown; + if (AuxArg.empty() || AuxArg == BottomUpArgStr) + Dir = SchedDirection::BottomUp; + else if (AuxArg == TopDownArgStr) + Dir = SchedDirection::TopDown; + else { + std::string ErrStr; + raw_string_ostream ErrSS(ErrStr); + ErrSS << "bottom-up-vec only supports '" << BottomUpArgStr << "' or '" + << TopDownArgStr << "' aux argument!\n"; + reportFatalUsageError(ErrStr.c_str()); + } } -public: - TopDownVec() : BottomUpVec("top-down-vec") {} + bool runOnRegion(Region &Rgn, const Analyses &A) final; }; } // namespace llvm::sandboxir diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp index 819d3415632f2..bde9416556f4d 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp @@ -681,7 +681,7 @@ bool BottomUpVec::runOnRegion(Region &Rgn, const Analyses &A) { LegalityAnalysis Legality(A.getAA(), A.getScalarEvolution(), F.getParent()->getDataLayout(), F.getContext(), *IMaps); - Legality.setDirection(getSchedDirection()); + Legality.setDirection(Dir); // TODO: Refactor to remove the unnecessary copy to SeedSliceVals. SmallVector<Value *> SeedSliceVals(SeedSlice.begin(), SeedSlice.end()); @@ -693,3 +693,4 @@ bool BottomUpVec::runOnRegion(Region &Rgn, const Analyses &A) { } // namespace sandboxir } // namespace llvm + diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def index 40d03c3886c0b..10ba595910ee9 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/PassRegistry.def @@ -26,7 +26,6 @@ REGION_PASS("tr-accept", ::llvm::sandboxir::TransactionAlwaysAccept) REGION_PASS("tr-revert", ::llvm::sandboxir::TransactionAlwaysRevert) REGION_PASS("tr-accept-or-revert", ::llvm::sandboxir::TransactionAcceptOrRevert) REGION_PASS("bottom-up-vec", ::llvm::sandboxir::BottomUpVec) -REGION_PASS("top-down-vec", ::llvm::sandboxir::TopDownVec) REGION_PASS("load-store-vec", ::llvm::sandboxir::LoadStoreVec) #undef REGION_PASS diff --git a/llvm/test/Transforms/SandboxVectorizer/external_uses.ll b/llvm/test/Transforms/SandboxVectorizer/external_uses.ll index 0bd6e9eebe5af..c15a413026ee8 100644 --- a/llvm/test/Transforms/SandboxVectorizer/external_uses.ll +++ b/llvm/test/Transforms/SandboxVectorizer/external_uses.ll @@ -1,6 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 6 ; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s -; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-collect-seeds=loads -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec(top-down),tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN ; Checks the handling of users outside the vectorized graph. @@ -18,10 +18,14 @@ define void @external_users(ptr %ptr) { ; TOPDOWN-LABEL: define void @external_users( ; TOPDOWN-SAME: ptr [[PTR:%.*]]) { ; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 -; TOPDOWN-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META0:![0-9]+]] -; TOPDOWN-NEXT: [[VEC:%.*]] = fsub <2 x float> [[VECL]], zeroinitializer, !sandboxvec [[META0]] -; TOPDOWN-NEXT: [[SUB0:%.*]] = extractelement <2 x float> [[VEC]], i32 0, !sandboxvec [[META0]] -; TOPDOWN-NEXT: store <2 x float> [[VEC]], ptr [[PTR0]], align 4, !sandboxvec [[META0]] +; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr float, ptr [[PTR]], i32 1 +; TOPDOWN-NEXT: [[LD0:%.*]] = load float, ptr [[PTR0]], align 4 +; TOPDOWN-NEXT: [[LD1:%.*]] = load float, ptr [[PTR1]], align 4 +; TOPDOWN-NEXT: [[SUB0:%.*]] = fsub float [[LD0]], 0.000000e+00 +; TOPDOWN-NEXT: [[SUB1:%.*]] = fsub float [[LD1]], 0.000000e+00 +; TOPDOWN-NEXT: [[PACK:%.*]] = insertelement <2 x float> poison, float [[SUB0]], i32 0, !sandboxvec [[META0:![0-9]+]] +; TOPDOWN-NEXT: [[PACK1:%.*]] = insertelement <2 x float> [[PACK]], float [[SUB1]], i32 1, !sandboxvec [[META0]] +; TOPDOWN-NEXT: store <2 x float> [[PACK1]], ptr [[PTR0]], align 4, !sandboxvec [[META0]] ; TOPDOWN-NEXT: [[USER:%.*]] = fneg float [[SUB0]] ; TOPDOWN-NEXT: ret void ; @@ -50,11 +54,11 @@ define void @external_user_of_constant(ptr %ptr, ptr %ptrX) { ; TOPDOWN-LABEL: define void @external_user_of_constant( ; TOPDOWN-SAME: ptr [[PTR:%.*]], ptr [[PTRX:%.*]]) { ; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 -; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr float, ptr [[PTR]], i32 1 ; TOPDOWN-NEXT: [[ZEXT0:%.*]] = zext i16 0 to i32 ; TOPDOWN-NEXT: [[ZEXT1:%.*]] = zext i16 0 to i32 -; TOPDOWN-NEXT: store i32 [[ZEXT0]], ptr [[PTR0]], align 4 -; TOPDOWN-NEXT: store i32 [[ZEXT1]], ptr [[PTR1]], align 4 +; TOPDOWN-NEXT: [[PACK:%.*]] = insertelement <2 x i32> poison, i32 [[ZEXT0]], i32 0, !sandboxvec [[META1:![0-9]+]] +; TOPDOWN-NEXT: [[PACK1:%.*]] = insertelement <2 x i32> [[PACK]], i32 [[ZEXT1]], i32 1, !sandboxvec [[META1]] +; TOPDOWN-NEXT: store <2 x i32> [[PACK1]], ptr [[PTR0]], align 4, !sandboxvec [[META1]] ; TOPDOWN-NEXT: store i32 [[ZEXT0]], ptr [[PTRX]], align 4 ; TOPDOWN-NEXT: ret void ; @@ -84,13 +88,16 @@ define void @vector_external_users(ptr %ptr) { ; TOPDOWN-SAME: ptr [[PTR:%.*]]) { ; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 ; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr float, ptr [[PTR]], i32 1 -; TOPDOWN-NEXT: [[VECL:%.*]] = load <3 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META1:![0-9]+]] -; TOPDOWN-NEXT: [[LD0:%.*]] = extractelement <3 x float> [[VECL]], i32 0, !sandboxvec [[META1]] -; TOPDOWN-NEXT: [[LD1:%.*]] = shufflevector <3 x float> [[VECL]], <3 x float> poison, <2 x i32> <i32 1, i32 2>, !sandboxvec [[META1]] +; TOPDOWN-NEXT: [[LD0:%.*]] = load float, ptr [[PTR0]], align 4 +; TOPDOWN-NEXT: [[LD1:%.*]] = load <2 x float>, ptr [[PTR1]], align 8 ; TOPDOWN-NEXT: [[SUB0:%.*]] = fsub float [[LD0]], 0.000000e+00 ; TOPDOWN-NEXT: [[SUB1:%.*]] = fsub <2 x float> [[LD1]], zeroinitializer -; TOPDOWN-NEXT: store float [[SUB0]], ptr [[PTR0]], align 4 -; TOPDOWN-NEXT: store <2 x float> [[SUB1]], ptr [[PTR1]], align 8 +; TOPDOWN-NEXT: [[PACK:%.*]] = insertelement <3 x float> poison, float [[SUB0]], i32 0, !sandboxvec [[META2:![0-9]+]] +; TOPDOWN-NEXT: [[VPACK:%.*]] = extractelement <2 x float> [[SUB1]], i32 0, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[VPACK1:%.*]] = insertelement <3 x float> [[PACK]], float [[VPACK]], i32 1, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[VPACK2:%.*]] = extractelement <2 x float> [[SUB1]], i32 1, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[VPACK3:%.*]] = insertelement <3 x float> [[VPACK1]], float [[VPACK2]], i32 2, !sandboxvec [[META2]] +; TOPDOWN-NEXT: store <3 x float> [[VPACK3]], ptr [[PTR0]], align 4, !sandboxvec [[META2]] ; TOPDOWN-NEXT: [[USER:%.*]] = fneg <2 x float> [[SUB1]] ; TOPDOWN-NEXT: ret void ; @@ -120,10 +127,20 @@ define void @vector_external_users_lane_and_index_differ(ptr %ptr) { ; TOPDOWN-LABEL: define void @vector_external_users_lane_and_index_differ( ; TOPDOWN-SAME: ptr [[PTR:%.*]]) { ; TOPDOWN-NEXT: [[PTR0:%.*]] = getelementptr <2 x float>, ptr [[PTR]], i32 0 -; TOPDOWN-NEXT: [[VECL:%.*]] = load <4 x float>, ptr [[PTR0]], align 8, !sandboxvec [[META2:![0-9]+]] -; TOPDOWN-NEXT: [[VEC:%.*]] = fsub <4 x float> [[VECL]], zeroinitializer, !sandboxvec [[META2]] -; TOPDOWN-NEXT: [[SUB1:%.*]] = shufflevector <4 x float> [[VEC]], <4 x float> poison, <2 x i32> <i32 2, i32 3>, !sandboxvec [[META2]] -; TOPDOWN-NEXT: store <4 x float> [[VEC]], ptr [[PTR0]], align 8, !sandboxvec [[META2]] +; TOPDOWN-NEXT: [[PTR1:%.*]] = getelementptr <2 x float>, ptr [[PTR]], i32 1 +; TOPDOWN-NEXT: [[LD0:%.*]] = load <2 x float>, ptr [[PTR0]], align 8 +; TOPDOWN-NEXT: [[LD1:%.*]] = load <2 x float>, ptr [[PTR1]], align 8 +; TOPDOWN-NEXT: [[SUB0:%.*]] = fsub <2 x float> [[LD0]], zeroinitializer +; TOPDOWN-NEXT: [[SUB1:%.*]] = fsub <2 x float> [[LD1]], zeroinitializer +; TOPDOWN-NEXT: [[VPACK:%.*]] = extractelement <2 x float> [[SUB0]], i32 0, !sandboxvec [[META3:![0-9]+]] +; TOPDOWN-NEXT: [[VPACK1:%.*]] = insertelement <4 x float> poison, float [[VPACK]], i32 0, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK2:%.*]] = extractelement <2 x float> [[SUB0]], i32 1, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK3:%.*]] = insertelement <4 x float> [[VPACK1]], float [[VPACK2]], i32 1, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK4:%.*]] = extractelement <2 x float> [[SUB1]], i32 0, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK5:%.*]] = insertelement <4 x float> [[VPACK3]], float [[VPACK4]], i32 2, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK6:%.*]] = extractelement <2 x float> [[SUB1]], i32 1, !sandboxvec [[META3]] +; TOPDOWN-NEXT: [[VPACK7:%.*]] = insertelement <4 x float> [[VPACK5]], float [[VPACK6]], i32 3, !sandboxvec [[META3]] +; TOPDOWN-NEXT: store <4 x float> [[VPACK7]], ptr [[PTR0]], align 8, !sandboxvec [[META3]] ; TOPDOWN-NEXT: [[USER:%.*]] = fneg <2 x float> [[SUB1]] ; TOPDOWN-NEXT: ret void ; @@ -148,4 +165,5 @@ define void @vector_external_users_lane_and_index_differ(ptr %ptr) { ; TOPDOWN: [[META0]] = distinct !{!"sandboxregion"} ; TOPDOWN: [[META1]] = distinct !{!"sandboxregion"} ; TOPDOWN: [[META2]] = distinct !{!"sandboxregion"} +; TOPDOWN: [[META3]] = distinct !{!"sandboxregion"} ;. diff --git a/llvm/test/Transforms/SandboxVectorizer/pack.ll b/llvm/test/Transforms/SandboxVectorizer/pack.ll index 6a91f3cdb5d24..925aa19def17b 100644 --- a/llvm/test/Transforms/SandboxVectorizer/pack.ll +++ b/llvm/test/Transforms/SandboxVectorizer/pack.ll @@ -1,6 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 ; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec,tr-accept>" %s -S | FileCheck %s -; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN +; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 -sbvec-always-verify -sbvec-passes="seed-collection<tr-save,bottom-up-vec(top-down),tr-accept>" %s -S | FileCheck %s --check-prefix=TOPDOWN define void @pack_constants(ptr %ptr) { ; CHECK-LABEL: define void @pack_constants( diff --git a/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll index 1f2b697c3b5b0..c98ad69e6107c 100644 --- a/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll +++ b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll @@ -1,7 +1,7 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5 ; RUN: opt -passes=sandbox-vectorizer -sbvec-vec-reg-bits=1024 -sbvec-allow-non-pow2 \ ; RUN: -sbvec-collect-seeds=loads -sbvec-always-verify \ -; RUN: -sbvec-passes="seed-collection<tr-save,top-down-vec,tr-accept>" \ +; RUN: -sbvec-passes="seed-collection<tr-save,bottom-up-vec(top-down),tr-accept>" \ ; RUN: %s -S | FileCheck %s ; Tests: successful bundle match (baseline) and !IMaps->isVectorized(UI0) on >From 606b9163898630d97fdccabe0c607ed8d3ddf5d3 Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Thu, 2 Jul 2026 14:35:08 -0400 Subject: [PATCH 5/6] [SandboxVec] Move user collection to VecUtils and add unit tests --- .../Vectorize/SandboxVectorizer/VecUtils.h | 9 + .../SandboxVectorizer/Passes/BottomUpVec.cpp | 56 +---- .../Vectorize/SandboxVectorizer/VecUtils.cpp | 54 +++++ .../SandboxVectorizer/VecUtilsTest.cpp | 226 ++++++++++++++++++ 4 files changed, 290 insertions(+), 55 deletions(-) diff --git a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h index 803718fc33792..a3fa0a36cb87f 100644 --- a/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h +++ b/llvm/include/llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h @@ -33,6 +33,8 @@ template <> struct DenseMapInfo<SmallVector<sandboxir::Value *>> { namespace sandboxir { +class InstrMaps; + class VecUtils { public: /// \Returns the number of elements in \p Ty. That is the number of lanes if a @@ -225,6 +227,13 @@ class VecUtils { /// \Returns the first integer power of 2 that is <= Num. LLVM_ABI static unsigned getFloorPowerOf2(unsigned Num); + /// From a user \p U0 of lane 0 (\p V0), try to form a bundle of matching + /// users for all lanes in \p Bndl. Returns an empty vector if no complete + /// bundle can be formed. + LLVM_ABI static SmallVector<Value *, 4> + getNextUserBundle(ArrayRef<Value *> Bndl, User *U0, Value *V0, + InstrMaps &IMaps); + /// Helper struct for `matchPack()`. Describes the instructions and operands /// of a pack pattern. struct PackPattern { diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp index bde9416556f4d..97a786b733956 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp @@ -36,7 +36,6 @@ static cl::opt<unsigned long> static constexpr unsigned long StopBundleDisabled = std::numeric_limits<unsigned long>::max(); - static cl::opt<unsigned long> StopBundle("sbvec-stop-bndl", cl::init(StopBundleDisabled), cl::Hidden, cl::desc("Vectorize up to this many bundles.")); @@ -281,58 +280,6 @@ void BottomUpVec::collectPotentiallyDeadInstrs(ArrayRef<Value *> Bndl) { } } -/// From a user \p U0 of lane 0 (\p V0), try to form a bundle of matching users -/// for all lanes in \p Bndl. Used by the top-down vectorizer only. Returns an -/// empty vector if no complete bundle can be formed. -static SmallVector<Value *, 4> getNextUserBundle(ArrayRef<Value *> Bndl, - User *U0, Value *V0, - InstrMaps &IMaps) { - auto *UI0 = dyn_cast<Instruction>(U0); - if (!UI0 || IMaps.isVectorized(UI0)) - return {}; - - // Find the operand index at which U0 uses lane 0. - unsigned OpIdx = UI0->getNumOperands(); - for (unsigned Idx : seq<unsigned>(UI0->getNumOperands())) { - if (UI0->getOperand(Idx) == V0) { - OpIdx = Idx; - break; - } - } - if (OpIdx == UI0->getNumOperands()) - return {}; - - // Find a distinct matching user for each of the remaining lanes. - SmallVector<Value *, 4> NextUserBndl; - NextUserBndl.push_back(UI0); - SmallPtrSet<Instruction *, 4> Claimed; - Claimed.insert(UI0); - for (Value *V : drop_begin(Bndl)) { - Instruction *Match = nullptr; - for (User *U : V->users()) { - auto *UI = dyn_cast<Instruction>(U); - if (!UI || IMaps.isVectorized(UI) || Claimed.contains(UI)) - continue; - if (UI->getOpcode() != UI0->getOpcode() || - UI->getType() != UI0->getType()) - continue; - // The whole bundle must live in the same block. - if (UI->getParent() != UI0->getParent()) - continue; - // The user must consume this lane at the same operand index. - if (OpIdx >= UI->getNumOperands() || UI->getOperand(OpIdx) != V) - continue; - Match = UI; - break; - } - if (!Match) - return {}; - Claimed.insert(Match); - NextUserBndl.push_back(Match); - } - return NextUserBndl; -} - Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, ArrayRef<Value *> UserBndl, unsigned Depth, LegalityAnalysis &Legality) { @@ -373,7 +320,7 @@ Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, Value *V0 = Bndl[0]; for (User *U0 : V0->users()) { SmallVector<Value *, 4> NextUserBndl = - getNextUserBundle(Bndl, U0, V0, *IMaps); + VecUtils::getNextUserBundle(Bndl, U0, V0, *IMaps); if (NextUserBndl.size() == Bndl.size()) vectorizeRec(NextUserBndl, Bndl, Depth + 1, Legality); } @@ -693,4 +640,3 @@ bool BottomUpVec::runOnRegion(Region &Rgn, const Analyses &A) { } // namespace sandboxir } // namespace llvm - diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/VecUtils.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/VecUtils.cpp index 6f9ef07e467d2..cd224dae2b081 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/VecUtils.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/VecUtils.cpp @@ -8,8 +8,62 @@ #include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h" +#include "llvm/ADT/Sequence.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/SandboxIR/Instruction.h" +#include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h" + namespace llvm::sandboxir { +SmallVector<Value *, 4> VecUtils::getNextUserBundle(ArrayRef<Value *> Bndl, + User *U0, Value *V0, + InstrMaps &IMaps) { + auto *UI0 = dyn_cast<Instruction>(U0); + if (!UI0 || IMaps.isVectorized(UI0)) + return {}; + + // Find the operand index at which U0 uses lane 0. + unsigned OpIdx = UI0->getNumOperands(); + for (unsigned Idx : seq<unsigned>(UI0->getNumOperands())) { + if (UI0->getOperand(Idx) == V0) { + OpIdx = Idx; + break; + } + } + if (OpIdx == UI0->getNumOperands()) + return {}; + + // Find a distinct matching user for each of the remaining lanes. + SmallVector<Value *, 4> NextUserBndl; + NextUserBndl.push_back(UI0); + SmallPtrSet<Instruction *, 4> Claimed; + Claimed.insert(UI0); + for (Value *V : drop_begin(Bndl)) { + Instruction *Match = nullptr; + for (User *U : V->users()) { + auto *UI = dyn_cast<Instruction>(U); + if (!UI || IMaps.isVectorized(UI) || Claimed.contains(UI)) + continue; + if (UI->getOpcode() != UI0->getOpcode() || + UI->getType() != UI0->getType()) + continue; + // The whole bundle must live in the same block. + if (UI->getParent() != UI0->getParent()) + continue; + // The user must consume this lane at the same operand index. + if (OpIdx >= UI->getNumOperands() || UI->getOperand(OpIdx) != V) + continue; + Match = UI; + break; + } + if (!Match) + return {}; + Claimed.insert(Match); + NextUserBndl.push_back(Match); + } + return NextUserBndl; +} + unsigned VecUtils::getFloorPowerOf2(unsigned Num) { if (Num == 0) return Num; diff --git a/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/VecUtilsTest.cpp b/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/VecUtilsTest.cpp index ea6cf7d45f525..c825092c4e0e9 100644 --- a/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/VecUtilsTest.cpp +++ b/llvm/unittests/Transforms/Vectorize/SandboxVectorizer/VecUtilsTest.cpp @@ -18,9 +18,11 @@ #include "llvm/IR/Dominators.h" #include "llvm/SandboxIR/Context.h" #include "llvm/SandboxIR/Function.h" +#include "llvm/SandboxIR/Instruction.h" #include "llvm/SandboxIR/Module.h" #include "llvm/SandboxIR/Type.h" #include "llvm/Support/SourceMgr.h" +#include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h" #include "gmock/gmock.h" #include "gtest/gtest.h" @@ -805,3 +807,227 @@ define void @foo(i32 %s0, <4 x i32> %v0, i32 %s1, <2 x i32> %v1, <3 x i32> %v2, EXPECT_EQ(Elms, Bndl); EXPECT_THAT(Lanes, testing::ElementsAre(0, 1, 5, 6, 8, 11)); } + +TEST_F(VecUtilsTest, GetNextUserBundle) { + parseIR(R"IR( +define void @match(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + %add1 = fadd float %ld1, %ld1 + ret void +} + +define void @opcode_mismatch(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + %sub1 = fsub float %ld1, %ld1 + ret void +} + +define void @type_mismatch(ptr %pf, ptr %pd) { +entry: + %f0 = load float, ptr %pf + %d1 = load double, ptr %pd + %add0 = fadd float %f0, %f0 + %add1 = fadd double %d1, %d1 + ret void +} + +define void @block_mismatch(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + br label %bb1 +bb1: + %add1 = fadd float %ld1, %ld1 + ret void +} + +define void @operand_mismatch(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld1 + %add1 = fadd float %ld0, %ld1 + ret void +} + +define void @missing_lane_user(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + ret void +} + +define void @vectorized_user(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + %add1 = fadd float %ld1, %ld1 + ret void +} + +define void @vectorized_seed_user(ptr %p) { +entry: + %gep0 = getelementptr float, ptr %p, i32 0 + %gep1 = getelementptr float, ptr %p, i32 1 + %ld0 = load float, ptr %gep0 + %ld1 = load float, ptr %gep1 + %add0 = fadd float %ld0, %ld0 + %add1 = fadd float %ld1, %ld1 + ret void +} +)IR"); + + auto withFunction = [this](StringRef FuncName, auto &&TestFn) { + sandboxir::Context Ctx(C); + sandboxir::InstrMaps IMaps; + auto *F = Ctx.createFunction(M->getFunction(FuncName)); + TestFn(*F, IMaps); + }; + + withFunction( + "match", [](sandboxir::Function &F, sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto *Add1 = &*It++; + + ASSERT_EQ(Add0->getOperand(0), Ld0); + ASSERT_EQ(Add1->getOperand(0), Ld1); + + auto run = [&](ArrayRef<sandboxir::Value *> Bndl, sandboxir::User *U0, + sandboxir::Value *V0, + ArrayRef<sandboxir::Instruction *> Expected) { + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle(Bndl, U0, V0, IMaps); + if (Expected.empty()) { + EXPECT_TRUE(NextUserBndl.empty()); + return; + } + ASSERT_EQ(NextUserBndl.size(), Expected.size()); + for (auto [Actual, Exp] : zip(NextUserBndl, Expected)) + EXPECT_EQ(Actual, Exp); + }; + + run({Ld0, Ld1}, Add0, Ld0, {Add0, Add1}); + run({Ld0, Ld1}, Add0, Ld1, {}); + }); + + withFunction("opcode_mismatch", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction( + "type_mismatch", [](sandboxir::Function &F, sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + auto *F0 = &*It++; + auto *D1 = &*It++; + auto *Add0 = &*It++; + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({F0, D1}, Add0, F0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction("block_mismatch", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &Entry = getBasicBlockByName(F, "entry"); + auto It = Entry.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction("operand_mismatch", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction("missing_lane_user", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction("vectorized_user", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + auto *Add1 = &*It++; + sandboxir::Action A(nullptr, {Add1}, {}, 0); + IMaps.registerVector({Add1}, &A); + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); + + withFunction("vectorized_seed_user", [](sandboxir::Function &F, + sandboxir::InstrMaps &IMaps) { + auto &BB = getBasicBlockByName(F, "entry"); + auto It = BB.begin(); + std::advance(It, 2); + auto *Ld0 = &*It++; + auto *Ld1 = &*It++; + auto *Add0 = &*It++; + sandboxir::Action A(nullptr, {Add0}, {}, 0); + IMaps.registerVector({Add0}, &A); + auto NextUserBndl = + sandboxir::VecUtils::getNextUserBundle({Ld0, Ld1}, Add0, Ld0, IMaps); + EXPECT_TRUE(NextUserBndl.empty()); + }); +} >From 4b62073f9fda73a80fd862b19fbbac19fa548c5d Mon Sep 17 00:00:00 2001 From: Anshil Gandhi <[email protected]> Date: Mon, 6 Jul 2026 13:54:06 -0400 Subject: [PATCH 6/6] Handle legality results --- .../SandboxVectorizer/Passes/BottomUpVec.cpp | 57 ++++++----- .../SandboxVectorizer/topdown_vec.ll | 98 +++++++++++++++++++ 2 files changed, 126 insertions(+), 29 deletions(-) diff --git a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp index 97a786b733956..fee793099bf7f 100644 --- a/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp +++ b/llvm/lib/Transforms/Vectorize/SandboxVectorizer/Passes/BottomUpVec.cpp @@ -296,41 +296,40 @@ Action *BottomUpVec::vectorizeRec(ArrayRef<Value *> Bndl, LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Legality: " << LegalityRes << "\n"); if (Legality.getDirection() == SchedDirection::TopDown) { + // A non-Widen result means we can't extend the vectorized region into + // this bundle, so leave its instructions scalar and don't record an + // action for it. The scalar users of the already-widened defs get their + // values through the unpacks emitted by emitUnpacksForExternalUses(). + // Note: The DiamondReuse* results are unreachable in the top-down + // direction because getNextUserBundle() skips already-vectorized users, + // so a bundle never contains instructions registered in IMaps. + if (LegalityRes.getSubclassID() != LegalityResultID::Widen) + return nullptr; + auto ActionPtr = std::make_unique<Action>(&LegalityRes, Bndl, ArrayRef<Value *>(), Depth); Action *Action = ActionPtr.get(); - if (LegalityRes.getSubclassID() == LegalityResultID::Widen) - IMaps->registerVector(Bndl, Action); + IMaps->registerVector(Bndl, Action); // Pre-order push so defs are before uses. Actions.push_back(std::move(ActionPtr)); - switch (LegalityRes.getSubclassID()) { - case LegalityResultID::Widen: { - // Walk down the def-use chain. Each lane in \p Bndl may feed several - // users, so we form every compatible user bundle and recurse into each - // one. A user bundle is compatible only if all of its users share the - // same opcode and type, live in the same block, are distinct and not - // already vectorized, and consume their corresponding element of \p Bndl - // at the same operand index, so that the widened vector lines up as a - // single vector operand. - // - // Recursing right after forming each bundle marks its instructions as - // vectorized (pre-order registration), which prevents sibling bundles - // from claiming the same instruction and guarantees termination. - Value *V0 = Bndl[0]; - for (User *U0 : V0->users()) { - SmallVector<Value *, 4> NextUserBndl = - VecUtils::getNextUserBundle(Bndl, U0, V0, *IMaps); - if (NextUserBndl.size() == Bndl.size()) - vectorizeRec(NextUserBndl, Bndl, Depth + 1, Legality); - } - break; - } - case LegalityResultID::DiamondReuse: - case LegalityResultID::DiamondReuseMultiInput: - case LegalityResultID::DiamondReuseWithShuffle: - case LegalityResultID::Pack: - llvm_unreachable("Not implemented."); + // Walk down the def-use chain. Each lane in \p Bndl may feed several + // users, so we form every compatible user bundle and recurse into each + // one. A user bundle is compatible only if all of its users share the + // same opcode and type, live in the same block, are distinct and not + // already vectorized, and consume their corresponding element of \p Bndl + // at the same operand index, so that the widened vector lines up as a + // single vector operand. + // + // Recursing right after forming each bundle marks its instructions as + // vectorized (pre-order registration), which prevents sibling bundles + // from claiming the same instruction and guarantees termination. + Value *V0 = Bndl[0]; + for (User *U0 : V0->users()) { + SmallVector<Value *, 4> NextUserBndl = + VecUtils::getNextUserBundle(Bndl, U0, V0, *IMaps); + if (NextUserBndl.size() == Bndl.size()) + vectorizeRec(NextUserBndl, Bndl, Depth + 1, Legality); } return Action; diff --git a/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll index c98ad69e6107c..786ff8584ee45 100644 --- a/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll +++ b/llvm/test/Transforms/SandboxVectorizer/topdown_vec.ll @@ -291,6 +291,101 @@ define void @user_already_vectorized(ptr %ptr, ptr %ptr2, float %a, float %b) { store float %fadd1b, ptr %ptr2_3, align 4 ret void } +; The fadd user bundle passes the getNextUserBundle() checks (same opcode, +; type, BB, operand index) but legality returns Pack due to different +; fast-math flags. The recursion must stop there: loads widen, fadds stay +; scalar and are fed by unpacks. +define void @user_diff_fast_math_flags(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @user_diff_fast_math_flags( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr float, ptr [[PTR2]], i32 1 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META9:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META9]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META9]] +; CHECK-NEXT: [[FADD0:%.*]] = fadd fast float [[UNPACK]], [[UNPACK]] +; CHECK-NEXT: [[FADD1:%.*]] = fadd float [[UNPACK1]], [[UNPACK1]] +; CHECK-NEXT: store float [[FADD0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store float [[FADD1]], ptr [[PTR2_1]], align 4 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr float, ptr %ptr2, i32 1 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + %fadd0 = fadd fast float %ld0, %ld0 + %fadd1 = fadd float %ld1, %ld1 + + store float %fadd0, ptr %ptr2_0, align 4 + store float %fadd1, ptr %ptr2_1, align 4 + ret void +} + +; Same as above but the user bundle packs due to different wrap flags +; (add nsw vs add). +define void @user_diff_wrap_flags(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @user_diff_wrap_flags( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr i32, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr i32, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_1:%.*]] = getelementptr i32, ptr [[PTR2]], i32 1 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x i32>, ptr [[PTR0]], align 4, !sandboxvec [[META10:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x i32> [[VECL]], i32 0, !sandboxvec [[META10]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x i32> [[VECL]], i32 1, !sandboxvec [[META10]] +; CHECK-NEXT: [[ADD0:%.*]] = add nsw i32 [[UNPACK]], 1 +; CHECK-NEXT: [[ADD1:%.*]] = add i32 [[UNPACK1]], 1 +; CHECK-NEXT: store i32 [[ADD0]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store i32 [[ADD1]], ptr [[PTR2_1]], align 4 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr i32, ptr %ptr, i32 0 + %ptr1 = getelementptr i32, ptr %ptr, i32 1 + %ptr2_0 = getelementptr i32, ptr %ptr2, i32 0 + %ptr2_1 = getelementptr i32, ptr %ptr2, i32 1 + + %ld0 = load i32, ptr %ptr0, align 4 + %ld1 = load i32, ptr %ptr1, align 4 + + %add0 = add nsw i32 %ld0, 1 + %add1 = add i32 %ld1, 1 + + store i32 %add0, ptr %ptr2_0, align 4 + store i32 %add1, ptr %ptr2_1, align 4 + ret void +} + +; The store user bundle forms but legality packs it because the stores are +; not consecutive (there is a gap in the destination). +define void @user_stores_not_consecutive(ptr %ptr, ptr %ptr2) { +; CHECK-LABEL: define void @user_stores_not_consecutive( +; CHECK-SAME: ptr [[PTR:%.*]], ptr [[PTR2:%.*]]) { +; CHECK-NEXT: [[PTR0:%.*]] = getelementptr float, ptr [[PTR]], i32 0 +; CHECK-NEXT: [[PTR2_0:%.*]] = getelementptr float, ptr [[PTR2]], i32 0 +; CHECK-NEXT: [[PTR2_2:%.*]] = getelementptr float, ptr [[PTR2]], i32 2 +; CHECK-NEXT: [[VECL:%.*]] = load <2 x float>, ptr [[PTR0]], align 4, !sandboxvec [[META11:![0-9]+]] +; CHECK-NEXT: [[UNPACK:%.*]] = extractelement <2 x float> [[VECL]], i32 0, !sandboxvec [[META11]] +; CHECK-NEXT: [[UNPACK1:%.*]] = extractelement <2 x float> [[VECL]], i32 1, !sandboxvec [[META11]] +; CHECK-NEXT: store float [[UNPACK]], ptr [[PTR2_0]], align 4 +; CHECK-NEXT: store float [[UNPACK1]], ptr [[PTR2_2]], align 4 +; CHECK-NEXT: ret void +; + %ptr0 = getelementptr float, ptr %ptr, i32 0 + %ptr1 = getelementptr float, ptr %ptr, i32 1 + %ptr2_0 = getelementptr float, ptr %ptr2, i32 0 + %ptr2_2 = getelementptr float, ptr %ptr2, i32 2 + + %ld0 = load float, ptr %ptr0, align 4 + %ld1 = load float, ptr %ptr1, align 4 + + store float %ld0, ptr %ptr2_0, align 4 + store float %ld1, ptr %ptr2_2, align 4 + ret void +} ;. ; CHECK: [[META0]] = distinct !{!"sandboxregion"} ; CHECK: [[META1]] = distinct !{!"sandboxregion"} @@ -301,4 +396,7 @@ define void @user_already_vectorized(ptr %ptr, ptr %ptr2, float %a, float %b) { ; CHECK: [[META6]] = distinct !{!"sandboxregion"} ; CHECK: [[META7]] = distinct !{!"sandboxregion"} ; CHECK: [[META8]] = distinct !{!"sandboxregion"} +; CHECK: [[META9]] = distinct !{!"sandboxregion"} +; CHECK: [[META10]] = distinct !{!"sandboxregion"} +; CHECK: [[META11]] = distinct !{!"sandboxregion"} ;. _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
