[DSE] Bugfix to avoid PartialStoreMerging involving non byte-sized stores

[bjope]

Summary

The DeadStoreElimination pass now skips doing
PartialStoreMerging when stores overlap according to
OW_PartialEarlierWithFullLater and at least one of
the stores is having a store size that is different
from the size of the type being stored.

This solves problems seen in

https://bugs.llvm.org/show_bug.cgi?id=41949

for which we in the past could end up with
mis-compiles or assertions.

The content and location of the padding bits is not
formally described (or undefined) in the LangRef
at the moment. So the solution is chosen based on
that we cannot assume anything about the padding bits
when having a store that clobbers more memory than
indicated by the type of the value that is stored
(such as storing an i6 using an 8-bit store instruction).

Fixes: https://bugs.llvm.org/show_bug.cgi?id=41949

[bjope]

Just a minor fix to use "Type *" instead of "auto *".

[efriedma]

Makes sense

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1211

cast<> instead of dyn_cast<>

1215

If we don't already have a helper for "getTypeStoreSizeInBits == getTypeSizeInBits", we should add one to DataLayout.

[bjope]

Add a helper in DataLayout "isTypeStoreSized()" as suggested in the review.
Open for suggestions regarding the name (or is it clear enough what it means?).

[bjope]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

1211

I no longer see a reason for calculating Earlier->getValueOperand()->getType() etc outside the if when using the new helper in DataLayout, so I reverted some of the refactoring in the last update. Also not sure if my earlier refactoring here was 100% safe.

[efriedma]

llvm/include/llvm/IR/DataLayout.h

460

The name you have is a little too short to be clear, I think; if you want something along those lines, maybe typeSizeEqualsStoreSize().

A couple other alternatives: hasNonStructPadding(), to indicate the underlying property of the memory. Or maybe follow EVT naming and call it isByteSized(), since this is essentially the same computation on a Type* instead of an EVT.

You could probably make this a little faster since getTypeStoreSizeInBits itself calls getTypeSizeInBits, but I guess it's unlikely to matter much.

[bjope]

Now calling the new helper in DataLayout typeSizeEqualsStoreSize().

(If this gets accepted I'll follow up with an NFC patch that is using the new helper in various places.)

[efriedma]

LGTM

llvm/include/llvm/IR/DataLayout.h

public:
   /// Returns the maximum number of bits that may be overwritten by
   /// storing the specified type; always a multiple of 8.
   ///
   /// For example, returns 40 for i36 and 80 for x86_fp80.
   uint64_t getTypeStoreSizeInBits(Type *Ty) const {
     return 8 * getTypeStoreSize(Ty);
   }
 
+  /// Returns true if no extra padding bits are needed when storing the
+  /// specified type.
+  ///
+  /// For example, returns false for i19 that has a 24-bit store size.
+  bool typeSizeEqualsStoreSize(Type *Ty) const {
+    return getTypeSizeInBits(Ty) == getTypeStoreSizeInBits(Ty);
+  }
+
   /// Returns the offset in bytes between successive objects of the
   /// specified type, including alignment padding.
   ///
   /// This is the amount that alloca reserves for this type. For example,
   /// returns 12 or 16 for x86_fp80, depending on alignment.
   uint64_t getTypeAllocSize(Type *Ty) const {
     // Round up to the next alignment boundary.
     return alignTo(getTypeStoreSize(Ty), getABITypeAlignment(Ty));

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

while (InstDep.isDef() || InstDep.isClobber()) {
           // The overwrite result is known, so these must be known, too.
           int64_t EarlierSize = DepLoc.Size.getValue();
           int64_t LaterSize = Loc.Size.getValue();
           bool IsOverwriteEnd = (OR == OW_End);
           MadeChange |= tryToShorten(DepWrite, DepWriteOffset, EarlierSize,
                                     InstWriteOffset, LaterSize, IsOverwriteEnd);
         } else if (EnablePartialStoreMerging &&
                    OR == OW_PartialEarlierWithFullLater) {
           auto *Earlier = dyn_cast<StoreInst>(DepWrite);
           auto *Later = dyn_cast<StoreInst>(Inst);
           if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&
+              DL.typeSizeEqualsStoreSize(
+                  Earlier->getValueOperand()->getType()) &&
               Later && isa<ConstantInt>(Later->getValueOperand()) &&
+              DL.typeSizeEqualsStoreSize(
+                  Later->getValueOperand()->getType()) &&
               memoryIsNotModifiedBetween(Earlier, Later, AA)) {
             // If the store we find is:
             //   a) partially overwritten by the store to 'Loc'
             //   b) the later store is fully contained in the earlier one and
             //   c) they both have a constant value
+            //   d) none of the two stores need padding
             // Merge the two stores, replacing the earlier store's value with a
             // merge of both values.
             // TODO: Deal with other constant types (vectors, etc), and probably
             // some mem intrinsics (if needed)
 
             APInt EarlierValue =
                 cast<ConstantInt>(Earlier->getValueOperand())->getValue();
             APInt LaterValue =

llvm/test/Transforms/DeadStoreElimination/PartialStore2.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s --data-layout "e" -dse -enable-dse-partial-store-merging=true -S | FileCheck --check-prefix CHECK --check-prefix CHECK-LE %s
+; RUN: opt < %s --data-layout "E" -dse -enable-dse-partial-store-merging=true -S | FileCheck --check-prefix CHECK --check-prefix CHECK-BE %s
+
+; This test used to hit an assertion (see PR41949).
+;
+; Better safe than sorry, do not assume anything about the padding for the
+; i28 store that has 32 bits as store size.
+define void @test1(i32* %p) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:    [[A:%.*]] = alloca i32
+; CHECK-NEXT:    [[B:%.*]] = bitcast i32* [[A]] to i28*
+; CHECK-NEXT:    [[C:%.*]] = bitcast i32* [[A]] to { i16, i16 }*
+; CHECK-NEXT:    [[C1:%.*]] = getelementptr inbounds { i16, i16 }, { i16, i16 }* [[C]], i32 0, i32 1
+; CHECK-NEXT:    store i28 10, i28* [[B]]
+; CHECK-NEXT:    store i16 20, i16* [[C1]]
+; CHECK-NEXT:    call void @test1(i32* [[A]])
+; CHECK-NEXT:    ret void
+;
+  %a = alloca i32
+  %b = bitcast i32* %a to i28*
+  %c = bitcast i32* %a to { i16, i16 }*
+  %c1 = getelementptr inbounds { i16, i16 }, { i16, i16 }* %c, i32 0, i32 1
+  store i28 10, i28* %b
+  store i16 20, i16* %c1
+
+  call void @test1(i32* %a)
+  ret void
+}
+
+
+; This test used to mis-compile (see PR41949).
+;
+; Better safe than sorry, do not assume anything about the padding for the
+; i12 store that has 16 bits as store size.
+define void @test2(i32* %p) {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:    [[U:%.*]] = alloca i32
+; CHECK-NEXT:    [[A:%.*]] = bitcast i32* [[U]] to i32*
+; CHECK-NEXT:    [[B:%.*]] = bitcast i32* [[U]] to i12*
+; CHECK-NEXT:    store i32 -1, i32* [[A]]
+; CHECK-NEXT:    store i12 20, i12* [[B]]
+; CHECK-NEXT:    call void @test2(i32* [[U]])
+; CHECK-NEXT:    ret void
+;
+  %u = alloca i32
+  %a = bitcast i32* %u to i32*
+  %b = bitcast i32* %u to i12*
+  store i32 -1, i32* %a
+  store i12 20, i12* %b
+
+  call void @test2(i32* %u)
+  ret void
+}
+