https://github.com/zGoldthorpe updated https://github.com/llvm/llvm-project/pull/222686
>From 9c0439b4e6b29afb9f303b7b1cb53dab40ded21a Mon Sep 17 00:00:00 2001 From: Zach Goldthorpe <[email protected]> Date: Wed, 9 Sep 2026 16:10:27 -0500 Subject: [PATCH 1/2] [LICM] Do not strip invariant AA tags --- llvm/lib/Transforms/Scalar/LICM.cpp | 55 ++++++++++++++++--- .../Transforms/LICM/scalar-promote-aa-tags.ll | 47 +++++++++------- 2 files changed, 75 insertions(+), 27 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp index 3e170264eea2d..0300ca94bcd9d 100644 --- a/llvm/lib/Transforms/Scalar/LICM.cpp +++ b/llvm/lib/Transforms/Scalar/LICM.cpp @@ -37,6 +37,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/LICM.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PriorityWorklist.h" #include "llvm/ADT/SetOperations.h" #include "llvm/ADT/Statistic.h" @@ -52,6 +53,7 @@ #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopNestAnalysis.h" #include "llvm/Analysis/LoopPass.h" +#include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MustExecute.h" @@ -2350,6 +2352,38 @@ static bool isPotentiallyPromotable(const Instruction *I, const Loop *L) { return false; } +/// Returns the potentially promotable stores with AA tags that are valid along +/// all non-unwinding execution paths of the loop \p L, which allows for the AA +/// tags to be used when deciding promotions. +static SmallPtrSet<const StoreInst *, 8> +collectStoresWithInvariantAATags(MemorySSA *MSSA, DominatorTree *DT, Loop *L) { + SmallDenseMap<MemoryLocation, SmallVector<const StoreInst *, 1>, 4> + StoresByLoc; + foreachMemoryAccess(MSSA, L, [&](Instruction *I) { + const auto *SI = dyn_cast<StoreInst>(I); + if (SI && SI->getAAMetadata() && isPotentiallyPromotable(SI, L)) + StoresByLoc[MemoryLocation::get(SI)].push_back(SI); + }); + + // This only looks at explicit exiting blocks. If we ever start sinking + // stores into unwind edges, this will break. + SmallVector<BasicBlock *, 4> ExitingBlocks; + L->getExitingBlocks(ExitingBlocks); + + SmallPtrSet<const StoreInst *, 8> StoresWithInvariantAATags; + for (const auto &Stores : llvm::make_second_range(StoresByLoc)) { + // Without exiting blocks the loop is never left, and promotion has no + // exit block to insert a store into either. + if (llvm::all_of(ExitingBlocks, [&](BasicBlock *ExitingBB) { + return llvm::any_of(Stores, [&](const StoreInst *SI) { + return DT->dominates(SI->getParent(), ExitingBB); + }); + })) + StoresWithInvariantAATags.insert_range(Stores); + } + return StoresWithInvariantAATags; +} + // The bool indicates whether there might be reads outside the set, in which // case only loads may be promoted. static SmallVector<PointersAndHasReadsOutsideSet, 0> @@ -2359,23 +2393,30 @@ collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, BatchAAResults BatchAA(*AA); AliasSetTracker AST(BatchAA); + // Only conditionally executed stores need this, so compute it on demand to + // keep the common case free. + std::optional<SmallPtrSet<const StoreInst *, 8>> StoresWithInvariantAATags; + auto HasInvariantAATags = [&](const StoreInst *SI) { + if (!SI->getAAMetadata()) + return false; + if (!StoresWithInvariantAATags) + StoresWithInvariantAATags = collectStoresWithInvariantAATags(MSSA, DT, L); + return StoresWithInvariantAATags->contains(SI); + }; + // Populate AST with potentially promotable accesses. SmallPtrSet<Value *, 16> AttemptingPromotion; foreachMemoryAccess(MSSA, L, [&](Instruction *I) { if (isPotentiallyPromotable(I, L)) { AttemptingPromotion.insert(I); if (StoreInst *SI = dyn_cast<StoreInst>(I); - SI && !SafetyInfo->isGuaranteedToExecute(*SI, DT)) { + SI && !SafetyInfo->isGuaranteedToExecute(*SI, DT) && + !HasInvariantAATags(SI)) { // Promotion requires inserting a new store at the loop exits; we need // to prove that store doesn't alias anything, in addition to proving // aliasing for the stores we're removing. The new store is executed // unconditionally, so when we're proving aliasing for that store, we - // can't rely on AA tags for stores which are conditionally executed. - // - // As a future improvement, we could avoid stripping AA tags in more - // cases. isGuaranteedToExecute() is stronger than what we need. - // We only need to prove that every exit from the loop is dominated - // by a store to the same location with the same AA tag. + // can only rely on AA tags that likewise hold unconditionally. AST.addWithoutAATags(SI); } else { AST.add(I); diff --git a/llvm/test/Transforms/LICM/scalar-promote-aa-tags.ll b/llvm/test/Transforms/LICM/scalar-promote-aa-tags.ll index ae6340ab51263..468cc9d554f6c 100644 --- a/llvm/test/Transforms/LICM/scalar-promote-aa-tags.ll +++ b/llvm/test/Transforms/LICM/scalar-promote-aa-tags.ll @@ -8,22 +8,24 @@ define i32 @promotable.store_dominates_exit_block(i64 %idx, i1 %c, i1 %c2) { ; CHECK-SAME: i64 [[IDX:%.*]], i1 [[C:%.*]], i1 [[C2:%.*]]) { ; CHECK-NEXT: [[ENTRY:.*]]: ; CHECK-NEXT: [[PTR:%.*]] = alloca [4 x i32], align 4 +; CHECK-NEXT: [[PTR_PROMOTED:%.*]] = load i32, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0:![0-9]+]] ; CHECK-NEXT: br label %[[LOOP:.*]] ; CHECK: [[LOOP]]: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ] -; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0:![0-9]+]] -; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[V]], 1 -; CHECK-NEXT: store i32 [[V_INC]], ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], %[[ENTRY]] ], [ [[TMP1:%.*]], %[[LATCH:.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH]] ] +; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[TMP0]], 1 ; CHECK-NEXT: [[FPTR:%.*]] = getelementptr float, ptr [[PTR]], i64 [[IV]] ; CHECK-NEXT: store float 0.000000e+00, ptr [[FPTR]], align 4, !tbaa [[FLOAT_TBAA4:![0-9]+]] ; CHECK-NEXT: br i1 [[C]], label %[[IF:.*]], label %[[LATCH]] ; CHECK: [[IF]]: -; CHECK-NEXT: store i32 0, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br label %[[LATCH]] ; CHECK: [[LATCH]]: +; CHECK-NEXT: [[TMP1]] = phi i32 [ 0, %[[IF]] ], [ [[V_INC]], %[[LOOP]] ] ; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 ; CHECK-NEXT: br i1 [[C2]], label %[[EXIT:.*]], label %[[LOOP]] ; CHECK: [[EXIT]]: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[TMP1]], %[[LATCH]] ] +; CHECK-NEXT: store i32 [[DOTLCSSA]], ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: [[RES:%.*]] = load i32, ptr [[PTR]], align 4 ; CHECK-NEXT: ret i32 [[RES]] ; @@ -166,15 +168,15 @@ define i32 @promotable.stores_jointly_dominate_exit_blocks(i64 %idx, i1 %c, i1 % ; CHECK-NEXT: store float 0.000000e+00, ptr [[FPTR]], align 4, !tbaa [[FLOAT_TBAA4]] ; CHECK-NEXT: br i1 [[C]], label %[[IF:.*]], label %[[ELSE:.*]] ; CHECK: [[IF]]: -; CHECK-NEXT: store i32 1, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br i1 [[C2]], label %[[EXIT:.*]], label %[[LATCH]] ; CHECK: [[ELSE]]: -; CHECK-NEXT: store i32 2, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br i1 [[C3]], label %[[EXIT]], label %[[LATCH]] ; CHECK: [[LATCH]]: ; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 ; CHECK-NEXT: br label %[[LOOP]] ; CHECK: [[EXIT]]: +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ 2, %[[ELSE]] ], [ 1, %[[IF]] ] +; CHECK-NEXT: store i32 [[TMP0]], ptr [[PTR]], align 1 ; CHECK-NEXT: [[RES:%.*]] = load i32, ptr [[PTR]], align 4 ; CHECK-NEXT: ret i32 [[RES]] ; @@ -266,15 +268,16 @@ define i32 @promotable.dominating_store_with_unwind(i64 %idx, i1 %c, i1 %c2) { ; CHECK-NEXT: [[FPTR:%.*]] = getelementptr float, ptr [[PTR]], i64 [[IV]] ; CHECK-NEXT: store float 0.000000e+00, ptr [[FPTR]], align 4, !tbaa [[FLOAT_TBAA4]] ; CHECK-NEXT: [[T:%.*]] = call i32 @opaque(i32 1) -; CHECK-NEXT: store i32 [[T]], ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br i1 [[C]], label %[[IF:.*]], label %[[LATCH]] ; CHECK: [[IF]]: -; CHECK-NEXT: store i32 0, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br label %[[LATCH]] ; CHECK: [[LATCH]]: +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ 0, %[[IF]] ], [ [[T]], %[[LOOP]] ] ; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 ; CHECK-NEXT: br i1 [[C2]], label %[[EXIT:.*]], label %[[LOOP]] ; CHECK: [[EXIT]]: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], %[[LATCH]] ] +; CHECK-NEXT: store i32 [[DOTLCSSA]], ptr [[PTR]], align 1 ; CHECK-NEXT: [[RES:%.*]] = load i32, ptr [[PTR]], align 4 ; CHECK-NEXT: ret i32 [[RES]] ; @@ -308,22 +311,24 @@ define i32 @promotable.noalias_store_dominates_exit_block(i64 %idx, i1 %c, i1 %c ; CHECK-SAME: i64 [[IDX:%.*]], i1 [[C:%.*]], i1 [[C2:%.*]]) { ; CHECK-NEXT: [[ENTRY:.*]]: ; CHECK-NEXT: [[PTR:%.*]] = alloca [4 x i32], align 4 +; CHECK-NEXT: [[PTR_PROMOTED:%.*]] = load i32, ptr [[PTR]], align 4, !noalias [[META8:![0-9]+]] ; CHECK-NEXT: br label %[[LOOP:.*]] ; CHECK: [[LOOP]]: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ] +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], %[[ENTRY]] ], [ [[TMP1:%.*]], %[[LATCH:.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH]] ] ; CHECK-NEXT: [[FPTR:%.*]] = getelementptr i32, ptr [[PTR]], i64 [[IV]] -; CHECK-NEXT: store i32 42, ptr [[FPTR]], align 4, !alias.scope [[META8:![0-9]+]] -; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[PTR]], align 4, !noalias [[META8]] -; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[V]], 1 -; CHECK-NEXT: store i32 [[V_INC]], ptr [[PTR]], align 4, !noalias [[META8]] +; CHECK-NEXT: store i32 42, ptr [[FPTR]], align 4, !alias.scope [[META8]] +; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[TMP0]], 1 ; CHECK-NEXT: br i1 [[C]], label %[[IF:.*]], label %[[LATCH]] ; CHECK: [[IF]]: -; CHECK-NEXT: store i32 0, ptr [[PTR]], align 4, !noalias [[META8]] ; CHECK-NEXT: br label %[[LATCH]] ; CHECK: [[LATCH]]: +; CHECK-NEXT: [[TMP1]] = phi i32 [ 0, %[[IF]] ], [ [[V_INC]], %[[LOOP]] ] ; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 ; CHECK-NEXT: br i1 [[C2]], label %[[EXIT:.*]], label %[[LOOP]] ; CHECK: [[EXIT]]: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[TMP1]], %[[LATCH]] ] +; CHECK-NEXT: store i32 [[DOTLCSSA]], ptr [[PTR]], align 4, !noalias [[META8]] ; CHECK-NEXT: [[RES:%.*]] = load i32, ptr [[PTR]], align 4 ; CHECK-NEXT: ret i32 [[RES]] ; @@ -357,22 +362,24 @@ define i32 @promotable.store_dominates_exit_block_non_thread_local_ptr(ptr %ptr, ; CHECK-LABEL: define i32 @promotable.store_dominates_exit_block_non_thread_local_ptr( ; CHECK-SAME: ptr [[PTR:%.*]], i64 [[IDX:%.*]], i1 [[C:%.*]], i1 [[C2:%.*]]) { ; CHECK-NEXT: [[ENTRY:.*]]: +; CHECK-NEXT: [[PTR_PROMOTED:%.*]] = load i32, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br label %[[LOOP:.*]] ; CHECK: [[LOOP]]: -; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH:.*]] ] +; CHECK-NEXT: [[TMP0:%.*]] = phi i32 [ [[PTR_PROMOTED]], %[[ENTRY]] ], [ [[TMP1:%.*]], %[[LATCH:.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[IDX]], %[[ENTRY]] ], [ [[IV_NEXT:%.*]], %[[LATCH]] ] ; CHECK-NEXT: [[FPTR:%.*]] = getelementptr float, ptr [[PTR]], i64 [[IV]] ; CHECK-NEXT: store float 0.000000e+00, ptr [[FPTR]], align 4, !tbaa [[FLOAT_TBAA4]] -; CHECK-NEXT: [[V:%.*]] = load i32, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] -; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[V]], 1 -; CHECK-NEXT: store i32 [[V_INC]], ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] +; CHECK-NEXT: [[V_INC:%.*]] = add i32 [[TMP0]], 1 ; CHECK-NEXT: br i1 [[C]], label %[[IF:.*]], label %[[LATCH]] ; CHECK: [[IF]]: -; CHECK-NEXT: store i32 0, ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: br label %[[LATCH]] ; CHECK: [[LATCH]]: +; CHECK-NEXT: [[TMP1]] = phi i32 [ 0, %[[IF]] ], [ [[V_INC]], %[[LOOP]] ] ; CHECK-NEXT: [[IV_NEXT]] = add i64 [[IV]], 1 ; CHECK-NEXT: br i1 [[C2]], label %[[EXIT:.*]], label %[[LOOP]] ; CHECK: [[EXIT]]: +; CHECK-NEXT: [[DOTLCSSA:%.*]] = phi i32 [ [[TMP1]], %[[LATCH]] ] +; CHECK-NEXT: store i32 [[DOTLCSSA]], ptr [[PTR]], align 4, !tbaa [[INT_TBAA0]] ; CHECK-NEXT: [[RES:%.*]] = load i32, ptr [[PTR]], align 4 ; CHECK-NEXT: ret i32 [[RES]] ; >From 4e15f15d91aa0fc06f58fb24a724319a0ecf0647 Mon Sep 17 00:00:00 2001 From: Zach Goldthorpe <[email protected]> Date: Thu, 10 Sep 2026 15:56:06 -0500 Subject: [PATCH 2/2] Check AA metadata before testing if guaranteed to execute --- llvm/lib/Transforms/Scalar/LICM.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp index 0300ca94bcd9d..da7c864d82a8b 100644 --- a/llvm/lib/Transforms/Scalar/LICM.cpp +++ b/llvm/lib/Transforms/Scalar/LICM.cpp @@ -2397,8 +2397,6 @@ collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, // keep the common case free. std::optional<SmallPtrSet<const StoreInst *, 8>> StoresWithInvariantAATags; auto HasInvariantAATags = [&](const StoreInst *SI) { - if (!SI->getAAMetadata()) - return false; if (!StoresWithInvariantAATags) StoresWithInvariantAATags = collectStoresWithInvariantAATags(MSSA, DT, L); return StoresWithInvariantAATags->contains(SI); @@ -2410,7 +2408,8 @@ collectPromotionCandidates(MemorySSA *MSSA, AliasAnalysis *AA, if (isPotentiallyPromotable(I, L)) { AttemptingPromotion.insert(I); if (StoreInst *SI = dyn_cast<StoreInst>(I); - SI && !SafetyInfo->isGuaranteedToExecute(*SI, DT) && + SI && SI->getAAMetadata() && + !SafetyInfo->isGuaranteedToExecute(*SI, DT) && !HasInvariantAATags(SI)) { // Promotion requires inserting a new store at the loop exits; we need // to prove that store doesn't alias anything, in addition to proving _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
