[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

1113–1115

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
if (AAR == AliasResult::MustAlias ||
       // 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();
struct DSEState {
   }
 
   /// Returns true if \p Def is not read before returning from the function.
   bool isWriteAtEndOfFunction(MemoryDef *Def) {
     LLVM_DEBUG(dbgs() << "  Check if def " << *Def << " ("
                       << *Def->getMemoryInst()
                       << ") is at the end the function \n");
 
-    auto MaybeLoc = getLocForWriteEx(Def->getMemoryInst());
+    Instruction *DefInst = Def->getMemoryInst();
+    auto MaybeLoc = getLocForWriteEx(DefInst);
     if (!MaybeLoc) {
       LLVM_DEBUG(dbgs() << "  ... could not get location for write.\n");
       return false;
     }
 
     SmallVector<MemoryAccess *, 4> WorkList;
     SmallPtrSet<MemoryAccess *, 8> Visited;
     auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
for (unsigned I = 0; I < WorkList.size(); I++) {
       // for example.
       // TODO: Add support for phi translation to handle the loop case.
       if (isa<MemoryPhi>(UseAccess))
         return false;
 
       // TODO: Checking for aliasing is expensive. Consider reducing the amount
       // of times this is called and/or caching it.
       Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
-      if (isReadClobber(*MaybeLoc, UseInst)) {
+      if (isReadClobber(DefInst, *MaybeLoc, 0, UseInst)) {
         LLVM_DEBUG(dbgs() << "  ... hit read clobber " << *UseInst << ".\n");
         return false;
       }
 
       if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
         PushMemUses(UseDef);
     }
     return true;
if (MaybeTermLoc->second) {
       const Value *LocUO = getUnderlyingObject(Loc.Ptr);
       return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
     }
     int64_t InstWriteOffset = 0;
     int64_t DepWriteOffset = 0;
     return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
                        DepWriteOffset) == OW_Complete;
   }
 
   // Returns true if \p Use may read from \p DefLoc.
-  bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
+  bool isReadClobber(Instruction *DefInst, const MemoryLocation &DefLoc,
+                     const int64_t DefOffset, Instruction *UseInst,
+                     Optional<MemoryLocation> UseLoc = None,
+                     const int64_t UseOffset = 0) {
     if (isNoopIntrinsic(UseInst))
       return false;
 
     // Monotonic or weaker atomic stores can be re-ordered and do not need to be
     // treated as read clobber.
     if (auto SI = dyn_cast<StoreInst>(UseInst))
       return isStrongerThan(SI->getOrdering(), AtomicOrdering::Monotonic);
 
     if (!UseInst->mayReadFromMemory())
       return false;
 
     if (auto *CB = dyn_cast<CallBase>(UseInst))
       if (CB->onlyAccessesInaccessibleMemory())
         return false;
 
+    if (!UseLoc) {
+      UseLoc = getLocForWriteEx(UseInst);
+      if (!UseLoc)
+        UseLoc = MemoryLocation::getOrNone(UseInst);
+    }
+
+    int64_t DummyDefOffset = DefOffset;
+    int64_t DummyUseOffset = UseOffset;
+    if (UseLoc &&
+        isOverwrite(DefInst, UseInst, DefLoc, *UseLoc, DummyUseOffset,
+                    DummyDefOffset) == OW_None)
+      return false;
+
     // NOTE: For calls, the number of stores removed could be slightly improved
     // by using AA.callCapturesBefore(UseInst, DefLoc, &DT), but that showed to
     // be expensive compared to the benefits in practice. For now, avoid more
     // expensive analysis to limit compile-time.
+    if (DefOffset == UseOffset)
       return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc));
+
+    return true;
   }
 
   /// Returns true if a dependency between \p Current and \p KillingDef is
   /// guaranteed to be loop invariant for the loops that they are in. Either
   /// because they are known to be in the same block, in the same loop level or
   /// by guaranteeing that \p CurrentLoc only references a single MemoryLocation
   /// during execution of the containing function.
   bool isGuaranteedLoopIndependent(const Instruction *Current,
for (;;
 
       // Check for anything that looks like it will be a barrier to further
       // removal
       if (isDSEBarrier(KillingUndObj, CurrentI)) {
         LLVM_DEBUG(dbgs() << "  ... skip, barrier\n");
         return None;
       }
 
+      // If Current does not have an analyzable write location, skip it
+      int64_t CurrOffset = 0;
+      CurrentLoc = getLocForWriteEx(CurrentI);
+      if (!CurrentLoc)
+        continue;
+
       // If Current is known to be on path that reads DefLoc or is a read
       // clobber, bail out, as the path is not profitable. We skip this check
       // for intrinsic calls, because the code knows how to handle memcpy
       // intrinsics.
-      if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
+      if (!isa<IntrinsicInst>(CurrentI) &&
+          isReadClobber(KillingI, KillingLoc, 0, CurrentI, CurrentLoc, 0))
         return None;
 
-      // Quick check if there are direct uses that are read-clobbers.
-      if (any_of(
-              CurrentAccess->uses(), [this, &KillingLoc, StartAccess](Use &U) {
-                if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
-                  return !MSSA.dominates(StartAccess, UseOrDef) &&
-                         isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
-                return false;
-              })) {
+      if (any_of(CurrentAccess->uses(), [this, KillingI, CurrentI, &KillingLoc,
+                                         PhiTransKillingLocAndOffset,
+                                         StartAccess](Use &U) {
+            if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser())) {
+              auto *UseInst = UseOrDef->getMemoryInst();
+              if (MSSA.dominates(StartAccess, UseOrDef))
+                return false;
+              // Use phi translated value for KillingLoc (from basic
+              // block of KillingI to CurrentI) only if UseInst is from
+              // the same basic block as CurrentI.
+              if (PhiTransKillingLocAndOffset &&
+                  UseInst->getParent() == CurrentI->getParent()) {
+                if (!isReadClobber(
+                        KillingI, (*PhiTransKillingLocAndOffset).first,
+                        (*PhiTransKillingLocAndOffset).second, UseInst)) {
+                  return false;
+                }
+              } else {
+                if (!isReadClobber(KillingI, KillingLoc, 0, UseInst)) {
+                  return false;
+                }
+              }
+              return true;
+            }
         LLVM_DEBUG(dbgs() << "   ...  found a read clobber\n");
         return None;
       }
 
       // If Current cannot be analyzed or is not removable, check the next
       // candidate.
       if (!hasAnalyzableMemoryWrite(CurrentI, TLI) || !isRemovable(CurrentI))
         continue;
 
-      // If Current does not have an analyzable write location, skip it
-      int64_t CurrOffset = 0;
-      CurrentLoc = getLocForWriteEx(CurrentI);
-      if (!CurrentLoc)
-        continue;
-
       // AliasAnalysis does not account for loops. Limit elimination to
       // candidates for which we can guarantee they always store to the same
       // memory location and not located in different loops.
       if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
         LLVM_DEBUG(dbgs() << "  ... not guaranteed loop independent\n");
         WalkerStepLimit -= 1;
         continue;
       }
for (unsigned I = 0; I < WorkList.size(); I++) {
         continue;
       }
 
       if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(KillingUndObj)) {
         LLVM_DEBUG(dbgs() << "  ... found throwing instruction\n");
         return None;
       }
 
-      // Uses which may read the original MemoryDef mean we cannot eliminate the
-      // original MD. Stop walk.
-      if (isReadClobber(MaybeDeadLoc, UseInst)) {
+      // Uses which may read the original KillingDef mean we cannot eliminate
+      // the original MD. Stop walk.
+      // Use phi translated value for KillingLoc (from basic block of
+      // KillingI to CurrentI) only if UseInst is from the same basic
+      // block as CurrentI.
+      if (PhiTransKillingLocAndOffset &&
+          UseInst->getParent() == MaybeDeadI->getParent()) {
+        if (isReadClobber(KillingI, (*PhiTransKillingLocAndOffset).first,
+                          (*PhiTransKillingLocAndOffset).second, UseInst)) {
           LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
           return None;
         }
+      } else {
+        if (isReadClobber(MaybeDeadI, MaybeDeadLoc, 0, UseInst)) {
+          LLVM_DEBUG(dbgs() << "    ... found read clobber\n");
+          return None;
+        }
+      }
 
       // If this worklist walks back to the original memory access (and the
       // pointer is not guarenteed loop invariant) then we cannot assume that a
       // store kills itself.
       if (MaybeDeadAccess == UseAccess &&
           !isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {
         LLVM_DEBUG(dbgs() << "    ... found not loop invariant self access\n");
         return None;