[DSE][WIP] Enable PHI translation to work through GEPs

[ebrevnov]

Summary

Current implementation of PHITransAddr::PHITranslateValue succeeds only if phi translated address has exact match in the predecessor (see code at PHITransAddr.cpp:237 for more details). In other words, it will fail to translate %p5 (and as a result optimize stores) in the following example:

BB1:
%p1 = ...
%p2 = GEP i8* %p1, 2
store i32* %p2, 0
...
BB3:
%p3 = phi([%p1, BB1], ....)
%p4 = GEP i8* %p3, 1
%p5 = bitcast i8*p3 to i16*
store %p5, 0

The solution is to traverse through GEPs (and maintain offsets) before calling PHITransAddr::PHITranslateValue.

[ebrevnov]

Fixed test failures

[ebrevnov]

Ping...

[ebrevnov]

Rebase

[ebrevnov]

Ping

[ebrevnov]

ping

[ebrevnov]

Ping

[fhahn]

It's hard to evaluate the impact of the change on its own. Is it strictly required for D90095 or could if be a follow-up to D90095 where we can show improvements on tests for this patch?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1088–1089

This comment needs updating, the if below now handles the must alias and partial alias case. The logic might be easier to follow & document if mustalias/partialalias logic would be kept separate, at the cost of minor code duplication.

[ebrevnov]

In D105105#3005752, @fhahn wrote:

It's hard to evaluate the impact of the change on its own. Is it strictly required for D90095 or could if be a follow-up to D90095 where we can show improvements on tests for this patch?

This should be doable. Do you want me to keep this as a separate NFC change or merge with functional change in PHI translation?

[fhahn]

In D105105#3008901, @ebrevnov wrote:

In D105105#3005752, @fhahn wrote:

It's hard to evaluate the impact of the change on its own. Is it strictly required for D90095 or could if be a follow-up to D90095 where we can show improvements on tests for this patch?

This should be doable. Do you want me to keep this as a separate NFC change or merge with functional change in PHI translation?

If possible, I think it would be best to update D90095 to not require this change. I assume this will mean some cases will be missed. Ideally this patch would then be a follow-up to D90095 where it is not NFC but has a functional impact and the impact is obvious from the test changes. Would that work?

[ebrevnov]

Include functional part exercizing non zero offsets. TODO: add tests.

[ebrevnov]

Wrong diff uploaded last time. Fixed now.

[ebrevnov]

Removed left offs after rebase

[ebrevnov]

Non-zero offsets should be allowed. Removing corresponding assert.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

 //===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // The code below implements dead store elimination using MemorySSA. It uses
static PhiTransPtr phiTranslatePtr(const PhiTransPtr &Ptr, BasicBlock *FromBB,
   }
 
   WorkList.push_back({FromBB, Ptr});
 
   while (!WorkList.empty()) {
     auto CurrNode = WorkList.pop_back_val();
     BasicBlock *CurrBB = CurrNode.first;
     const PhiTransPtr &CurrPtr = CurrNode.second;
+    int64_t Offset = 0;
+    Value *const BasePtr =
+        GetPointerBaseWithConstantOffset(CurrPtr.first, Offset, DL);
+    const int64_t BaseOffset = CurrPtr.second + Offset;
 
     for (pred_iterator PI = pred_begin(CurrBB), E = pred_end(CurrBB); PI != E;
          ++PI) {
       BasicBlock *PredBB = *PI;
-      PHITransAddr TransAddr{CurrPtr.first, DL, AC};
+      PHITransAddr TransAddr{BasePtr, DL, AC};
 
       // TODO:
       if (!DT.dominates(ToBB, PredBB))
         continue;
 
       if (TransAddr.NeedsPHITranslationFromBlock(CurrBB) &&
           (!TransAddr.IsPotentiallyPHITranslatable() ||
            TransAddr.PHITranslateValue(CurrBB, PredBB, &DT, false)))
         return PhiTransPtr{};
 
       auto Inserted =
-          Visited.try_emplace(PredBB, TransAddr.getAddr(), CurrPtr.second);
+          Visited.try_emplace(PredBB, TransAddr.getAddr(), BaseOffset);
       auto &TransPtr = Inserted.first->second;
       if (!Inserted.second) {
         if (TransAddr.getAddr() != TransPtr.first ||
-            CurrPtr.second != TransPtr.second)
+            BaseOffset != TransPtr.second)
           // We already visited this block before. If it was with a different
           // address - bail out!
           return PhiTransPtr{};
         continue;
       }
 
       if (PredBB == ToBB) {
         ResPtr = TransPtr;
         continue;
       }
 
       WorkList.push_back({PredBB, TransPtr});
     }
   }
 
   assert(ResPtr.first.pointsToAliveValue() &&
          "PHI translation is expected to complete successfully");
-  assert(ResPtr.second == 0 &&
-         "Unexpected non-zero offset during phi translation");
   return ResPtr;
 }
 
 static ExMemoryAccess
 phiTransFromMemoryAccessTo(const ExMemoryAccess &FromAccess,
                            MemoryAccess *ToAccess, const DataLayout &DL,
                            DominatorTree &DT, AssumptionCache *AC) {
   PhiTransPtr ResAddr;
struct DSEState {
 
   /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
   /// KillingI instruction) completely overwrites a store to the 'DeadLoc'
   /// location (by \p DeadI instruction).
   /// Return OW_MaybePartial if \p KillingI does not completely overwrite
   /// \p DeadI, but they both write to the same underlying object. In that
   /// case, use isPartialOverwrite to check if \p KillingI partially overwrites
   /// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
+  /// Parameters:
+  ///   KillingI/DeadI - Instructions accessing \p KillingLoc/DeadLoc memory
+  ///     locations
+  ///   KillingLoc/DeadLoc - Memory locations under question
+  ///   KillingOff/DeadOff [in, out] - On input, may provide initial offset of
+  ///     access relative to KillingLoc/DeadLoc memory location. On output, if
+  ///     returned value is not "OW_Unknown" will keep absolute offset of access
+  ///     relative to some common base of KillingLoc and DeadLoc locations.
   OverwriteResult isOverwrite(const Instruction *KillingI,
                               const Instruction *DeadI,
                               const MemoryLocation &KillingLoc,
                               const MemoryLocation &DeadLoc,
                               int64_t &KillingOff, int64_t &DeadOff) {
     // AliasAnalysis does not always account for loops. Limit overwrite checks
     // to dependencies for which we can guarantee they are independent of any
     // loops they are in.
     if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
       return OW_Unknown;
 
     // FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
     // get imprecise values here, though (except for unknown sizes).
     if (!KillingLoc.Size.isPrecise() || !DeadLoc.Size.isPrecise()) {
       // In case no constant size is known, try to an IR values for the number
       // of bytes written and check if they match.
       const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
       const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
       if (KillingMemI && DeadMemI) {
         const Value *KillingV = KillingMemI->getLength();
         const Value *DeadV = DeadMemI->getLength();
-        if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))
+        if (KillingV == DeadV && KillingOff == DeadOff &&
+            BatchAA.isMustAlias(DeadLoc, KillingLoc))
           return OW_Complete;
       }
 
       // Masked stores have imprecise locations, but we can reason about them
       // to some extent.
       return isMaskedStoreOverwrite(KillingI, DeadI, BatchAA);
     }
 
     const uint64_t KillingSize = KillingLoc.Size.getValue();
     const uint64_t DeadSize = DeadLoc.Size.getValue();
 
     // Query the alias information
     AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);
 
-    // If the start pointers are the same, we just have to compare sizes to see if
-    // the killing store was larger than the dead store.
-    if (AAR == AliasResult::MustAlias) {
-      // Make sure that the KillingSize size is >= the DeadSize size.
-      if (KillingSize >= DeadSize)
+    // If the start pointers are the same, it's enough to compare sizes and
+    // offsets to see if the killing store fully overwrites the dead one.
+    if (AAR == AliasResult::MustAlias ||
+        (AAR == AliasResult::PartialAlias && AAR.hasOffset() &&
+         AAR.getOffset() >= 0)) {
+      int64_t AdjEarlierOff =
+          DeadOff + (AAR == AliasResult::PartialAlias ? AAR.getOffset() : 0);
+      // Make sure that the dead access is "inside" the killing one.
+      if (AdjEarlierOff >= KillingOff &&
+          uint64_t(AdjEarlierOff - KillingOff) + DeadSize <= KillingSize) {
+        DeadOff = AdjEarlierOff;
         return OW_Complete;
       }
-
-    // If we hit a partial alias we may have a full overwrite
-    if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
-      int32_t Off = AAR.getOffset();
-      if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)
-        return OW_Complete;
     }
 
     // Check to see if the killing store is to the entire object (either a
     // global, an alloca, or a byval/inalloca argument).  If so, then it clearly
     // overwrites any other store to the same object.
     const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
     const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
     const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
     const Value *KillingUndObj = getUnderlyingObject(KillingPtr);
 
     // If we can't resolve the same pointers to the same object, then we can't
     // analyze them at all.
     if (DeadUndObj != KillingUndObj)
       return OW_Unknown;
 
     // If the KillingI store is to a recognizable object, get its size.
     uint64_t KillingUndObjSize = getPointerSize(KillingUndObj, DL, TLI, &F);
     if (KillingUndObjSize != MemoryLocation::UnknownSize)
       if (KillingUndObjSize == KillingSize && KillingUndObjSize >= DeadSize)
         return OW_Complete;
 
     // Okay, we have stores to two completely different pointers.  Try to
-    // decompose the pointer into a "base + constant_offset" form.  If the base
-    // pointers are equal, then we can reason about the two stores.
-    DeadOff = 0;
-    KillingOff = 0;
+    // decompose the pointer into a "base + constant_offset" form.  If the
+    // base pointers are equal, then we can reason about the two stores.
+    int64_t ExtraDeadOff = 0;
+    int64_t ExtraKillingOff = 0;
     const Value *DeadBasePtr =
-        GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);
+        GetPointerBaseWithConstantOffset(DeadPtr, ExtraDeadOff, DL);
     const Value *KillingBasePtr =
-        GetPointerBaseWithConstantOffset(KillingPtr, KillingOff, DL);
+        GetPointerBaseWithConstantOffset(KillingPtr, ExtraKillingOff, DL);
+    DeadOff += ExtraDeadOff;
+    KillingOff += ExtraKillingOff;
 
     // If the base pointers still differ, we have two completely different
     // stores.
     if (DeadBasePtr != KillingBasePtr)
       return OW_Unknown;
 
     // The killing access completely overlaps the dead store if and only if
     // both start and end of the dead one is "inside" the killing one:
bool isCompleteOverwrite(const MemoryLocation &DefLoc, Instruction *DefInst,
     // MemoryDef.
     if (!UseInst->mayWriteToMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
-    int64_t InstWriteOffset, DepWriteOffset;
+    int64_t InstWriteOffset = 0;
+    int64_t DepWriteOffset = 0;
     if (auto CC = getLocForWriteEx(UseInst))
       return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,
                          DepWriteOffset) == OW_Complete;
     return false;
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
for (;;
           continue;
       } else {
         auto &KillingMemLoc = PhiTransKillingLocAndOffset
                                   ? (*PhiTransKillingLocAndOffset).first
                                   : KillingLoc;
         int64_t KillingMemOffset = PhiTransKillingLocAndOffset
                                        ? (*PhiTransKillingLocAndOffset).second
                                        : 0;
-        assert(KillingMemOffset == 0 && "Unexpected non-zero offset");
         auto OR = isOverwrite(KillingI, CurrentI, KillingMemLoc, *CurrentLoc,
                               KillingMemOffset, CurrOffset);
         // If Current does not write to the same object as KillingDef, check
         // the next candidate.
         if (OR == OW_Unknown)
           continue;
         else if (OR == OW_MaybePartial) {
           // If KillingDef only partially overwrites Current, check the next
while (!ToCheck.empty()) {
         int64_t KillingOffset = 0;
         int64_t DeadOffset = 0;
 
         if (ExDeadAccess.second.first.pointsToAliveValue()) {
           KillingLoc = KillingLoc.getWithNewPtr(ExDeadAccess.second.first)
                       .getWithoutAATags();
           KillingOffset = ExDeadAccess.second.second;
         }
-        assert(KillingOffset == 0 && "Unexpected non-zero offset");
 
         OverwriteResult OR = State.isOverwrite(
             KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
         if (OR == OW_MaybePartial) {
           auto Iter = State.IOLs.insert(
               std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
                   DeadI->getParent(), InstOverlapIntervalsTy()));
           auto &IOL = Iter.first->second;