https://github.com/eas updated https://github.com/llvm/llvm-project/pull/219058
>From 8b5ecfa82339b23787d8570485bb58e9b8f11bee Mon Sep 17 00:00:00 2001 From: Andrei Elovikov <[email protected]> Date: Wed, 26 Aug 2026 12:10:09 -0700 Subject: [PATCH] [VPlan] Use compact RPOT instead of just RPOT This is necessary for the future partial linearization change, but I wanted to commit this bit independently because it changes some tests on itself and could potentially provide more blend optimization opportunites (at least I hoped) but that didn't seem to happen. --- .../Transforms/Vectorize/VPlanPredicator.cpp | 73 +++++++++++++++---- .../LoopVectorize/VPlan/predicator.ll | 60 +++++++-------- .../LoopVectorize/X86/predicate-switch.ll | 8 +- .../Transforms/LoopVectorize/predicator.ll | 8 +- 4 files changed, 96 insertions(+), 53 deletions(-) diff --git a/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp b/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp index 063b0fb22882e..8374f254eaf4e 100644 --- a/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanPredicator.cpp @@ -20,18 +20,58 @@ #include "VPlanUtils.h" #include "llvm/ADT/PostOrderIterator.h" +#define DEBUG_TYPE "vplan-predicator" + using namespace llvm; using namespace VPlanPatternMatch; namespace { +class CompactRPOT { + SmallVector<VPBlockBase *> Blocks; + DenseMap<const VPBlockBase *, unsigned> BlockIndex; + + template <typename rpo_iterator> + void scheduleDomRegion(VPBlockBase *VPBB, rpo_iterator It, rpo_iterator End, + unsigned &NextIndex, const VPDominatorTree &VPDT) { + BlockIndex[VPBB] = NextIndex++; + for (; It != End; ++It) { + auto *DTNode = VPDT.getNode(*It); + if (DTNode->getIDom()->getBlock() != VPBB) + continue; + scheduleDomRegion(*It, It, End, NextIndex, VPDT); + } + } + +public: + CompactRPOT(VPBasicBlock *Header, const VPDominatorTree &VPDT) { + copy(post_order(VPBlockShallowTraversalWrapper<VPBlockBase *>{Header}), + std::back_inserter(Blocks)); + unsigned Index = 0; + // Blocks are in post-order (not reversed), so use reverse iterators while + // compacting. + scheduleDomRegion(*Blocks.rbegin(), Blocks.rbegin(), Blocks.rend(), Index, + VPDT); + sort(Blocks, [&](VPBlockBase *A, VPBlockBase *B) { + return BlockIndex[A] < BlockIndex[B]; + }); + + LLVM_DEBUG({ + dbgs() << "Compact RPOT: "; + for (VPBlockBase *VPBB : Blocks) { + dbgs() << " " << VPBB->getName(); + } + dbgs() << "\n"; + }); + } + + auto begin() const { return Blocks.begin(); } + auto end() const { return Blocks.end(); } + unsigned getIndex(const VPBlockBase *BB) const { return BlockIndex.at(BB); } +}; + class VPPredicator { VPlan &Plan; - // Scan the body of the loop in a topological order to visit each basic - // block after having visited its predecessor basic blocks. - ReversePostOrderTraversal<VPBlockShallowTraversalWrapper<VPBlockBase *>> RPOT; - DenseMap<const VPBlockBase *, unsigned> BlockIndex; - /// Builder to construct recipes to compute masks. VPBuilder Builder; @@ -41,6 +81,10 @@ class VPPredicator { /// Post-dominator tree for the VPlan. VPPostDominatorTree VPPDT; + // Scan the body of the loop in a topological order to visit each basic + // block after having visited its predecessor basic blocks. + CompactRPOT BlocksInCompactRPOTOrder; + /// When we if-convert we need to create edge masks. We have to cache values /// so that we don't end up with exponential recursion/IR. using EdgeMaskCacheTy = @@ -110,12 +154,9 @@ class VPPredicator { public: VPPredicator(VPlan &Plan) - : Plan(Plan), RPOT(Plan.getVectorLoopRegion()->getEntryBasicBlock()), - VPDT(Plan), VPPDT(Plan) { - for (auto [Idx, BB] : enumerate(RPOT)) { - BlockIndex[BB] = Idx; - } - } + : Plan(Plan), VPDT(Plan), VPPDT(Plan), + BlocksInCompactRPOTOrder( + Plan.getVectorLoopRegion()->getEntryBasicBlock(), VPDT) {} /// Returns the *entry* mask for \p VPBB. VPValue *getBlockInMask(const VPBasicBlock *VPBB) const { @@ -349,7 +390,8 @@ VPPredicator::computeBlendTerms(VPPhi *Phi) const { Terms.emplace_back(V, cast<VPBasicBlock>(VPBB)); sort(Terms, [this](const BlendTermTy &L, const BlendTermTy &R) { - return BlockIndex.lookup(L.second) < BlockIndex.lookup(R.second); + return BlocksInCompactRPOTOrder.getIndex(L.second) < + BlocksInCompactRPOTOrder.getIndex(R.second); }); assert(all_of(zip(Terms, drop_begin(Terms)), [](const auto &Pair) { @@ -452,7 +494,7 @@ void VPPredicator::convertPhisToBlends(VPBasicBlock *VPBB) { void VPPredicator::run() { VPBasicBlock *Header = Plan.getVectorLoopRegion()->getEntryBasicBlock(); - for (VPBlockBase *VPB : RPOT) { + for (VPBlockBase *VPB : BlocksInCompactRPOTOrder) { // Non-outer regions with VPBBs only are supported at the moment. auto *VPBB = cast<VPBasicBlock>(VPB); // Introduce the mask for VPBB, which may introduce needed edge masks, and @@ -472,13 +514,14 @@ void VPPredicator::run() { } } - for (VPBlockBase *VPBB : reverse(RPOT)) + for (VPBlockBase *VPBB : reverse(BlocksInCompactRPOTOrder)) if (VPBB != Header) convertPhisToBlends(cast<VPBasicBlock>(VPBB)); // Linearize the blocks of the loop into one serial chain. VPBlockBase *PrevVPBB = nullptr; - for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) { + for (VPBasicBlock *VPBB : + VPBlockUtils::blocksOnly<VPBasicBlock>(BlocksInCompactRPOTOrder)) { auto Successors = to_vector(VPBB->getSuccessors()); if (Successors.size() > 1) VPBB->getTerminator()->eraseFromParent(); diff --git a/llvm/test/Transforms/LoopVectorize/VPlan/predicator.ll b/llvm/test/Transforms/LoopVectorize/VPlan/predicator.ll index 94cb32491fdfe..86597a10bd7b8 100644 --- a/llvm/test/Transforms/LoopVectorize/VPlan/predicator.ll +++ b/llvm/test/Transforms/LoopVectorize/VPlan/predicator.ll @@ -290,30 +290,30 @@ define void @switch(ptr %a) { ; CHECK-EMPTY: ; CHECK-NEXT: bb1: ; CHECK-NEXT: EMIT ir<%add1> = add ir<%iv>, ir<1>, ir<%c0> +; CHECK-NEXT: Successor(s): bb4 +; CHECK-EMPTY: +; CHECK-NEXT: bb4: +; CHECK-NEXT: EMIT vp<[[VP5:%[0-9]+]]> = icmp eq ir<%iv>, ir<1> +; CHECK-NEXT: EMIT vp<[[VP6:%[0-9]+]]> = icmp eq ir<%iv>, ir<2> +; CHECK-NEXT: EMIT vp<[[VP7:%[0-9]+]]> = icmp eq ir<%iv>, ir<3> +; CHECK-NEXT: EMIT vp<[[VP8:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP5]]> +; CHECK-NEXT: EMIT vp<[[VP9:%[0-9]+]]> = or vp<[[VP6]]>, vp<[[VP7]]> +; CHECK-NEXT: EMIT vp<[[VP10:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP9]]> +; CHECK-NEXT: EMIT vp<[[VP11:%[0-9]+]]> = or vp<[[VP8]]>, vp<[[VP10]]> +; CHECK-NEXT: EMIT vp<[[VP12:%[0-9]+]]> = not vp<[[VP11]]> +; CHECK-NEXT: EMIT vp<[[VP13:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP12]]> +; CHECK-NEXT: EMIT ir<%add4> = add ir<%iv>, ir<4>, vp<[[VP8]]> ; CHECK-NEXT: Successor(s): bb3 ; CHECK-EMPTY: ; CHECK-NEXT: bb3: -; CHECK-NEXT: EMIT vp<[[VP5:%[0-9]+]]> = logical-and vp<[[VP4]]>, ir<%c2> -; CHECK-NEXT: EMIT vp<[[VP6:%[0-9]+]]> = icmp eq ir<%iv>, ir<1> -; CHECK-NEXT: EMIT vp<[[VP7:%[0-9]+]]> = icmp eq ir<%iv>, ir<2> -; CHECK-NEXT: EMIT vp<[[VP8:%[0-9]+]]> = icmp eq ir<%iv>, ir<3> -; CHECK-NEXT: EMIT vp<[[VP9:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP6]]> -; CHECK-NEXT: EMIT vp<[[VP10:%[0-9]+]]> = or vp<[[VP7]]>, vp<[[VP8]]> -; CHECK-NEXT: EMIT vp<[[VP11:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP10]]> -; CHECK-NEXT: EMIT vp<[[VP12:%[0-9]+]]> = or vp<[[VP9]]>, vp<[[VP11]]> -; CHECK-NEXT: EMIT vp<[[VP13:%[0-9]+]]> = not vp<[[VP12]]> -; CHECK-NEXT: EMIT vp<[[VP14:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP13]]> -; CHECK-NEXT: EMIT vp<[[VP15:%[0-9]+]]> = or vp<[[VP5]]>, vp<[[VP11]]> +; CHECK-NEXT: EMIT vp<[[VP14:%[0-9]+]]> = logical-and vp<[[VP4]]>, ir<%c2> +; CHECK-NEXT: EMIT vp<[[VP15:%[0-9]+]]> = or vp<[[VP14]]>, vp<[[VP10]]> ; CHECK-NEXT: BLEND ir<%phi3> = ir<%add2>/vp<[[VP4]]> ir<%add1>/ir<%c0> ; CHECK-NEXT: EMIT ir<%add3> = add ir<%phi3>, ir<3>, vp<[[VP15]]> -; CHECK-NEXT: Successor(s): bb4 -; CHECK-EMPTY: -; CHECK-NEXT: bb4: -; CHECK-NEXT: EMIT ir<%add4> = add ir<%iv>, ir<4>, vp<[[VP9]]> ; CHECK-NEXT: Successor(s): bb5 ; CHECK-EMPTY: ; CHECK-NEXT: bb5: -; CHECK-NEXT: BLEND ir<%phi5> = ir<%add2>/vp<[[VP4]]> ir<%add1>/ir<%c0> ir<%add3>/vp<[[VP15]]> ir<%add4>/vp<[[VP9]]> +; CHECK-NEXT: BLEND ir<%phi5> = ir<%add2>/vp<[[VP4]]> ir<%add1>/ir<%c0> ir<%add4>/vp<[[VP8]]> ir<%add3>/vp<[[VP15]]> ; CHECK-NEXT: EMIT store ir<%phi5>, ir<%gep> ; CHECK-NEXT: EMIT ir<%iv.next> = add nuw nsw ir<%iv>, ir<1> ; CHECK-NEXT: EMIT ir<%ec> = icmp eq ir<%iv.next>, ir<128> @@ -488,29 +488,29 @@ define void @blend_masks(ptr noalias %p, i1 %c0, i1 %c1, i1 %c2, i1 %c3, i1 %c4) ; CHECK-NEXT: bb4: ; CHECK-NEXT: EMIT vp<[[VP5:%[0-9]+]]> = not ir<%c1> ; CHECK-NEXT: EMIT vp<[[VP6:%[0-9]+]]> = logical-and ir<%c0>, vp<[[VP5]]> -; CHECK-NEXT: Successor(s): bb6 -; CHECK-EMPTY: -; CHECK-NEXT: bb6: -; CHECK-NEXT: EMIT vp<[[VP7:%[0-9]+]]> = not ir<%c3> -; CHECK-NEXT: EMIT vp<[[VP8:%[0-9]+]]> = logical-and vp<[[VP6]]>, vp<[[VP7]]> -; CHECK-NEXT: EMIT vp<[[VP9:%[0-9]+]]> = or vp<[[VP8]]>, vp<[[VP4]]> ; CHECK-NEXT: Successor(s): bb3 ; CHECK-EMPTY: ; CHECK-NEXT: bb3: -; CHECK-NEXT: EMIT vp<[[VP10:%[0-9]+]]> = logical-and ir<%c0>, ir<%c1> +; CHECK-NEXT: EMIT vp<[[VP7:%[0-9]+]]> = logical-and ir<%c0>, ir<%c1> ; CHECK-NEXT: Successor(s): bb5 ; CHECK-EMPTY: ; CHECK-NEXT: bb5: -; CHECK-NEXT: EMIT vp<[[VP11:%[0-9]+]]> = logical-and vp<[[VP6]]>, ir<%c3> -; CHECK-NEXT: EMIT vp<[[VP12:%[0-9]+]]> = not ir<%c2> -; CHECK-NEXT: EMIT vp<[[VP13:%[0-9]+]]> = logical-and vp<[[VP10]]>, vp<[[VP12]]> -; CHECK-NEXT: EMIT vp<[[VP14:%[0-9]+]]> = or vp<[[VP11]]>, vp<[[VP13]]> +; CHECK-NEXT: EMIT vp<[[VP8:%[0-9]+]]> = logical-and vp<[[VP6]]>, ir<%c3> +; CHECK-NEXT: EMIT vp<[[VP9:%[0-9]+]]> = not ir<%c2> +; CHECK-NEXT: EMIT vp<[[VP10:%[0-9]+]]> = logical-and vp<[[VP7]]>, vp<[[VP9]]> +; CHECK-NEXT: EMIT vp<[[VP11:%[0-9]+]]> = or vp<[[VP8]]>, vp<[[VP10]]> +; CHECK-NEXT: Successor(s): bb6 +; CHECK-EMPTY: +; CHECK-NEXT: bb6: +; CHECK-NEXT: EMIT vp<[[VP12:%[0-9]+]]> = not ir<%c3> +; CHECK-NEXT: EMIT vp<[[VP13:%[0-9]+]]> = logical-and vp<[[VP6]]>, vp<[[VP12]]> +; CHECK-NEXT: EMIT vp<[[VP14:%[0-9]+]]> = or vp<[[VP13]]>, vp<[[VP4]]> ; CHECK-NEXT: Successor(s): bb7 ; CHECK-EMPTY: ; CHECK-NEXT: bb7: -; CHECK-NEXT: EMIT vp<[[VP15:%[0-9]+]]> = logical-and vp<[[VP9]]>, ir<%c4> -; CHECK-NEXT: EMIT vp<[[VP16:%[0-9]+]]> = or vp<[[VP15]]>, vp<[[VP14]]> -; CHECK-NEXT: BLEND ir<%phi> = ir<1>/vp<[[VP9]]> ir<0>/vp<[[VP14]]> +; CHECK-NEXT: EMIT vp<[[VP15:%[0-9]+]]> = logical-and vp<[[VP14]]>, ir<%c4> +; CHECK-NEXT: EMIT vp<[[VP16:%[0-9]+]]> = or vp<[[VP15]]>, vp<[[VP11]]> +; CHECK-NEXT: BLEND ir<%phi> = ir<0>/vp<[[VP11]]> ir<1>/vp<[[VP14]]> ; CHECK-NEXT: EMIT ir<%gep> = getelementptr ir<%p>, ir<%iv> ; CHECK-NEXT: EMIT store ir<%phi>, ir<%gep>, vp<[[VP16]]> ; CHECK-NEXT: Successor(s): bb8 diff --git a/llvm/test/Transforms/LoopVectorize/X86/predicate-switch.ll b/llvm/test/Transforms/LoopVectorize/X86/predicate-switch.ll index 8f9039b9db32f..8d3d058fbdf4e 100644 --- a/llvm/test/Transforms/LoopVectorize/X86/predicate-switch.ll +++ b/llvm/test/Transforms/LoopVectorize/X86/predicate-switch.ll @@ -1140,6 +1140,10 @@ define void @br_under_switch_default_common_dest_with_case(ptr %start, ptr %end, ; FORCED-NEXT: [[TMP15:%.*]] = xor <4 x i1> [[TMP13]], splat (i1 true) ; FORCED-NEXT: [[TMP16:%.*]] = icmp ule <4 x i64> [[WIDE_LOAD]], [[BROADCAST_SPLAT]] ; FORCED-NEXT: [[TMP17:%.*]] = icmp ule <4 x i64> [[WIDE_LOAD3]], [[BROADCAST_SPLAT]] +; FORCED-NEXT: [[TMP24:%.*]] = select <4 x i1> [[TMP8]], <4 x i1> [[TMP16]], <4 x i1> zeroinitializer +; FORCED-NEXT: [[TMP25:%.*]] = select <4 x i1> [[TMP9]], <4 x i1> [[TMP17]], <4 x i1> zeroinitializer +; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> splat (i64 42), ptr align 1 [[NEXT_GEP]], <4 x i1> [[TMP24]]) +; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> splat (i64 42), ptr align 1 [[TMP7]], <4 x i1> [[TMP25]]) ; FORCED-NEXT: [[TMP18:%.*]] = xor <4 x i1> [[TMP16]], splat (i1 true) ; FORCED-NEXT: [[TMP19:%.*]] = xor <4 x i1> [[TMP17]], splat (i1 true) ; FORCED-NEXT: [[TMP20:%.*]] = select <4 x i1> [[TMP8]], <4 x i1> [[TMP18]], <4 x i1> zeroinitializer @@ -1148,10 +1152,6 @@ define void @br_under_switch_default_common_dest_with_case(ptr %start, ptr %end, ; FORCED-NEXT: [[TMP23:%.*]] = or <4 x i1> [[TMP21]], [[TMP11]] ; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> zeroinitializer, ptr align 1 [[NEXT_GEP]], <4 x i1> [[TMP22]]) ; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> zeroinitializer, ptr align 1 [[TMP7]], <4 x i1> [[TMP23]]) -; FORCED-NEXT: [[TMP24:%.*]] = select <4 x i1> [[TMP8]], <4 x i1> [[TMP16]], <4 x i1> zeroinitializer -; FORCED-NEXT: [[TMP25:%.*]] = select <4 x i1> [[TMP9]], <4 x i1> [[TMP17]], <4 x i1> zeroinitializer -; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> splat (i64 42), ptr align 1 [[NEXT_GEP]], <4 x i1> [[TMP24]]) -; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> splat (i64 42), ptr align 1 [[TMP7]], <4 x i1> [[TMP25]]) ; FORCED-NEXT: [[TMP26:%.*]] = or <4 x i1> [[TMP24]], [[TMP14]] ; FORCED-NEXT: [[TMP27:%.*]] = or <4 x i1> [[TMP25]], [[TMP15]] ; FORCED-NEXT: call void @llvm.masked.store.v4i64.p0(<4 x i64> splat (i64 2), ptr align 1 [[NEXT_GEP]], <4 x i1> [[TMP26]]) diff --git a/llvm/test/Transforms/LoopVectorize/predicator.ll b/llvm/test/Transforms/LoopVectorize/predicator.ll index 7f18c312912df..b9b41ce2b01e0 100644 --- a/llvm/test/Transforms/LoopVectorize/predicator.ll +++ b/llvm/test/Transforms/LoopVectorize/predicator.ll @@ -94,17 +94,17 @@ define void @blend_masks(ptr noalias %p, i1 %c0, i1 %c1, i1 %c3, i1 %c4, i1 %c6) ; CHECK-NEXT: [[TMP0:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT8]], splat (i1 true) ; CHECK-NEXT: [[TMP1:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT6]], splat (i1 true) ; CHECK-NEXT: [[TMP2:%.*]] = select <4 x i1> [[BROADCAST_SPLAT8]], <4 x i1> [[TMP1]], <4 x i1> zeroinitializer -; CHECK-NEXT: [[TMP3:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT4]], splat (i1 true) -; CHECK-NEXT: [[TMP4:%.*]] = select <4 x i1> [[TMP2]], <4 x i1> [[TMP3]], <4 x i1> zeroinitializer -; CHECK-NEXT: [[TMP5:%.*]] = or <4 x i1> [[TMP4]], [[TMP0]] ; CHECK-NEXT: [[TMP6:%.*]] = select <4 x i1> [[BROADCAST_SPLAT8]], <4 x i1> [[BROADCAST_SPLAT6]], <4 x i1> zeroinitializer ; CHECK-NEXT: [[TMP7:%.*]] = select <4 x i1> [[TMP2]], <4 x i1> [[BROADCAST_SPLAT4]], <4 x i1> zeroinitializer ; CHECK-NEXT: [[TMP8:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT]], splat (i1 true) ; CHECK-NEXT: [[TMP9:%.*]] = select <4 x i1> [[TMP6]], <4 x i1> [[TMP8]], <4 x i1> zeroinitializer ; CHECK-NEXT: [[TMP10:%.*]] = or <4 x i1> [[TMP7]], [[TMP9]] +; CHECK-NEXT: [[TMP13:%.*]] = xor <4 x i1> [[BROADCAST_SPLAT4]], splat (i1 true) +; CHECK-NEXT: [[TMP14:%.*]] = select <4 x i1> [[TMP2]], <4 x i1> [[TMP13]], <4 x i1> zeroinitializer +; CHECK-NEXT: [[TMP5:%.*]] = or <4 x i1> [[TMP14]], [[TMP0]] ; CHECK-NEXT: [[TMP11:%.*]] = select <4 x i1> [[TMP5]], <4 x i1> [[BROADCAST_SPLAT2]], <4 x i1> zeroinitializer ; CHECK-NEXT: [[TMP12:%.*]] = or <4 x i1> [[TMP11]], [[TMP10]] -; CHECK-NEXT: [[PREDPHI:%.*]] = select <4 x i1> [[TMP10]], <4 x i32> zeroinitializer, <4 x i32> splat (i32 1) +; CHECK-NEXT: [[PREDPHI:%.*]] = select <4 x i1> [[TMP5]], <4 x i32> splat (i32 1), <4 x i32> zeroinitializer ; CHECK-NEXT: br label %[[PRED_STORE_CONTINUE12:.*]] ; CHECK: [[PRED_STORE_CONTINUE12]]: ; CHECK-NEXT: [[TMP26:%.*]] = phi i32 [ 0, %[[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], %[[PRED_STORE_CONTINUE12]] ] _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
