[DSE] Check for whole object overwrite even if dead store size not known

[nikic]

Summary

If the killing store overwrites the whole object, we know that the preceding store is dead, regardless of the accessed offset or size. This case was previously only handled if the size of the dead store was also known.

This allows us to perform conventional DSE for calls that write to an argument (but without known size).

[reames]

LGTM, and thanks for following up on my observation on the other review.

The old code would leave around a write larger than the object size even if the entire object was killed later. That in theory would let us discover the UB, but I think that was purely an accident in the code. We could explicitly handle the UB case before checking for deadness if desired.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

OverwriteResult isOverwrite(const Instruction *KillingI,
                               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;
 
+    const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
+    const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
+    const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
+    const Value *KillingUndObj = getUnderlyingObject(KillingPtr);
+
+    // Check whether the killing store overwrites the whole object, in which
+    // case the size/offset of the dead store does not matter.
+    if (DeadUndObj == KillingUndObj && KillingLoc.Size.isPrecise()) {
+      uint64_t KillingUndObjSize = getPointerSize(KillingUndObj, DL, TLI, &F);
+      if (KillingUndObjSize != MemoryLocation::UnknownSize &&
+          KillingUndObjSize == KillingLoc.Size.getValue())
+        return OW_Complete;
+    }
+
     // 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) {
OverwriteResult isOverwrite(const Instruction *KillingI,
 
     // 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) {
       // Non aliasing stores to different objects don't overlap. Note that
       // if the killing store is known to overwrite whole object (out of
       // bounds access overwrites whole object as well) then it is assumed to
       // completely overwrite any store to the same object even if they don't
       // actually alias (see next check).
       if (AAR == AliasResult::NoAlias)
         return OW_None;
       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;
     const Value *DeadBasePtr =
         GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);
     const Value *KillingBasePtr =

llvm/test/Transforms/DeadStoreElimination/trivial-dse-calls.ll

 ; CHECK-NEXT:    ret void
 ;
   %a = alloca i32, align 4
   %bitcast = bitcast i32* %a to i8*
   call void @f2(i8* nocapture writeonly %bitcast, i8* nocapture readonly %bitcast) argmemonly nounwind willreturn
   ret void
 }
 
-; TODO: We should be able to remove the call because while we don't know
-; the size of the write done by the call, we do know the following store
-; writes to the entire contents of the alloca.
+; We can remove the call because while we don't know the size of the write done
+; by the call, we do know the following store writes to the entire contents of
+; the alloca.
 define i32 @test_dse_overwrite() {
 ; CHECK-LABEL: @test_dse_overwrite(
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
-; CHECK-NEXT:    [[BITCAST:%.*]] = bitcast i32* [[A]] to i8*
-; CHECK-NEXT:    call void @f(i8* nocapture writeonly [[BITCAST]]) #[[ATTR1]]
 ; CHECK-NEXT:    store i32 0, i32* [[A]], align 4
 ; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[A]], align 4
 ; CHECK-NEXT:    ret i32 [[V]]
 ;
   %a = alloca i32, align 4
   %bitcast = bitcast i32* %a to i8*
   call void @f(i8* writeonly nocapture %bitcast) argmemonly nounwind willreturn
   store i32 0, i32* %a