git: c7e5a0d42f20 - stable/13 - Merge commit 28a2b85602a5 from llvm-project (by Kazu Hirata):

From: Dimitry Andric <dim_at_FreeBSD.org>
Date: Sun, 28 Jul 2024 11:05:11 UTC
The branch stable/13 has been updated by dim:

URL: https://cgit.FreeBSD.org/src/commit/?id=c7e5a0d42f20e9a81b96fc89b3b9883cf4be9839

commit c7e5a0d42f20e9a81b96fc89b3b9883cf4be9839
Author:     Dimitry Andric <dim@FreeBSD.org>
AuthorDate: 2024-07-25 11:13:45 +0000
Commit:     Dimitry Andric <dim@FreeBSD.org>
CommitDate: 2024-07-28 11:04:26 +0000

    Merge commit 28a2b85602a5 from llvm-project (by Kazu Hirata):
    
      [DeadStoreElimination] Use SmallSetVector (NFC) (#79410)
    
      The use of SmallSetVector saves 0.58% of heap allocations during the
      compilation of a large preprocessed file, namely X86ISelLowering.cpp,
      for the X86 target.  During the experiment, the final size of ToCheck
      was 8 or less 88% of the time.
    
    Merge commit 9e95c4947d31 from llvm-project (by Nikita Popov):
    
      [DSE] Fix non-determinism due to address reuse (#84943)
    
      The malloc->calloc fold creates a new MemoryAccess, which may end of at
      the same address as a previously deleted access inside SkipStores.
    
      To the most part, this is not a problem, because SkipStores is normally
      only used together with MemDefs. Neither the old malloc access nor the
      new calloc access will be part of MemDefs, so there is no problem here.
    
      However, SkipStores is also used in one more place: In the main DSE
      loop, ToCheck entries are checked against it. Fix this by not using
      SkipStores here, and instead using a separate set to track deletions
      inside this loop. This way it is not affected by the calloc optimization
      that happens outside it.
    
      This is all pretty ugly, but I haven't found another good way to fix it.
      Suggestions welcome.
    
      No test case as I don't have a reliable DSE-only test-case for this.
    
      Fixes https://github.com/llvm/llvm-project/issues/84458.
    
    This fixes another possible difference in output when building i386
    object files with a native or cross build of clang. (Specifically, the
    file sbin/ipf/ipmon/ipmon.o.)
    
    PR:             276961
    Reported by:    cperciva
    MFC after:      3 days
    
    (cherry picked from commit 55a2a91c5e1bb39dd625ba56597608883fbcb318)
---
 .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 24 ++++++++++++++++------
 1 file changed, 18 insertions(+), 6 deletions(-)

diff --git a/contrib/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/contrib/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
index 380d65836553..f0f0f5f28025 100644
--- a/contrib/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/contrib/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -1697,7 +1697,9 @@ struct DSEState {
 
   /// Delete dead memory defs and recursively add their operands to ToRemove if
   /// they became dead.
-  void deleteDeadInstruction(Instruction *SI) {
+  void
+  deleteDeadInstruction(Instruction *SI,
+                        SmallPtrSetImpl<MemoryAccess *> *Deleted = nullptr) {
     MemorySSAUpdater Updater(&MSSA);
     SmallVector<Instruction *, 32> NowDeadInsts;
     NowDeadInsts.push_back(SI);
@@ -1718,6 +1720,8 @@ struct DSEState {
         if (IsMemDef) {
           auto *MD = cast<MemoryDef>(MA);
           SkipStores.insert(MD);
+          if (Deleted)
+            Deleted->insert(MD);
           if (auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
             if (SI->getValueOperand()->getType()->isPointerTy()) {
               const Value *UO = getUnderlyingObject(SI->getValueOperand());
@@ -2111,7 +2115,12 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
     unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
     unsigned PartialLimit = MemorySSAPartialStoreLimit;
     // Worklist of MemoryAccesses that may be killed by KillingDef.
-    SetVector<MemoryAccess *> ToCheck;
+    SmallSetVector<MemoryAccess *, 8> ToCheck;
+    // Track MemoryAccesses that have been deleted in the loop below, so we can
+    // skip them. Don't use SkipStores for this, which may contain reused
+    // MemoryAccess addresses.
+    SmallPtrSet<MemoryAccess *, 8> Deleted;
+    [[maybe_unused]] unsigned OrigNumSkipStores = State.SkipStores.size();
     ToCheck.insert(KillingDef->getDefiningAccess());
 
     bool Shortend = false;
@@ -2119,7 +2128,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
     // Check if MemoryAccesses in the worklist are killed by KillingDef.
     for (unsigned I = 0; I < ToCheck.size(); I++) {
       MemoryAccess *Current = ToCheck[I];
-      if (State.SkipStores.count(Current))
+      if (Deleted.contains(Current))
         continue;
 
       std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
@@ -2166,7 +2175,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
           continue;
         LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DeadI
                           << "\n  KILLER: " << *KillingI << '\n');
-        State.deleteDeadInstruction(DeadI);
+        State.deleteDeadInstruction(DeadI, &Deleted);
         ++NumFastStores;
         MadeChange = true;
       } else {
@@ -2203,7 +2212,7 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
               Shortend = true;
               // Remove killing store and remove any outstanding overlap
               // intervals for the updated store.
-              State.deleteDeadInstruction(KillingSI);
+              State.deleteDeadInstruction(KillingSI, &Deleted);
               auto I = State.IOLs.find(DeadSI->getParent());
               if (I != State.IOLs.end())
                 I->second.erase(DeadSI);
@@ -2215,13 +2224,16 @@ static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
         if (OR == OW_Complete) {
           LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n  DEAD: " << *DeadI
                             << "\n  KILLER: " << *KillingI << '\n');
-          State.deleteDeadInstruction(DeadI);
+          State.deleteDeadInstruction(DeadI, &Deleted);
           ++NumFastStores;
           MadeChange = true;
         }
       }
     }
 
+    assert(State.SkipStores.size() - OrigNumSkipStores == Deleted.size() &&
+           "SkipStores and Deleted out of sync?");
+
     // Check if the store is a no-op.
     if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
       LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *KillingI