[DAGCombine] Fold overlapping constant stores

[niravd]

Summary

Fold a smaller constant store into larger constant stores immediately
preceeding it.

[rnk]

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

67

Why zero initialize here but not in the other call site? It gives the impression that it reads it as an input, but it doesn't.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15445

Implementing this FIXME is just a matter of changing the Offset * 8 calculation below, right? And, updating test cases, of course. If so, I think it's easy enough to be worth implementing just for completeness.

[niravd]

Add big endian support and rebase past added big and little endian test case.

[courbet]

LGTM

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

15441

nit: preceding (here and elsewhere)

15454

clang-format ?

[niravd]

LGTMed, but not accepted. Presumably oversight, but address nits and clang format just in case.

[lebedev.ri]

I *think* this likely caused https://bugs.llvm.org/show_bug.cgi?id=43446

[lebedev.ri]

In D58468#1731906, @lebedev.ri wrote:

I *think* this likely caused https://bugs.llvm.org/show_bug.cgi?id=43446

Reverted in rGd20907d1de89bf63b589fadd8c096d4895e47fba.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/include/llvm/CodeGen/SelectionDAGAddressAnalysis.h

bool equalBaseIndex(const BaseIndexOffset &Other,
                       const SelectionDAG &DAG) const {
     int64_t Off;
     return equalBaseIndex(Other, DAG, Off);
   }
 
   // Returns true if `Other` (with size `OtherSize`) can be proven to be fully
   // contained in `*this` (with size `Size`).
   bool contains(int64_t Size, const BaseIndexOffset &Other, int64_t OtherSize,
-                const SelectionDAG &DAG) const;
+                const SelectionDAG &DAG) const {
+    int64_t Offset;
+    return contains(Size, Other, OtherSize, DAG, Offset);
+  }
+
+  bool contains(int64_t Size, const BaseIndexOffset &Other, int64_t OtherSize,
+                const SelectionDAG &DAG, int64_t &Offset) const;
 
   // Returns true `BasePtr0` and `BasePtr1` can be proven to alias/not alias, in
   // which case `IsAlias` is set to true/false.
   static bool computeAliasing(const BaseIndexOffset &BasePtr0,
                               const int64_t NumBytes0,
                               const BaseIndexOffset &BasePtr1,
                               const int64_t NumBytes1, const SelectionDAG &DAG,
                               bool &IsAlias);

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (ST->isUnindexed() && !ST->isVolatile() && ST1->isUnindexed() &&
         // If this is a store who's preceeding store to a subset of the current
         // location and no one other node is chained to that store we can
         // effectively drop the store. Do not remove stores to undef as they may
         // be used as data sinks.
         if (STBase.contains(STByteSize, ChainBase, ChainByteSize, DAG)) {
           CombineTo(ST1, ST1->getChain());
           return SDValue();
         }
+
+        // If ST stores to a subset of preceeding store's write set, we may be
+        // able to fold ST's value into the preceeding stored value. As we know
+        // the other uses of ST1's chain are unconcerned with ST, this folding
+        // will not affect those nodes.
+        int64_t Offset;
+        if (ChainBase.contains(ChainByteSize, STBase, STByteSize, DAG,
+                               Offset)) {
+          SDValue ChainValue = ST1->getValue();
+          if (auto *C1 = dyn_cast<ConstantSDNode>(ChainValue)) {
+            if (auto *C = dyn_cast<ConstantSDNode>(Value)) {
+              APInt Val = C1->getAPIntValue();
+              APInt InsertVal = C->getAPIntValue().zextOrTrunc(STByteSize * 8);
+              if (DAG.getDataLayout().isBigEndian())
+                Offset = ChainByteSize - 1 - Offset;
+              Val.insertBits(InsertVal, Offset * 8);
+              SDValue NewSDVal =
+                  DAG.getConstant(Val, SDLoc(C), ChainValue.getValueType(),
+                                  C1->isTargetOpcode(), C1->isOpaque());
+              SDNode *NewST1 = DAG.UpdateNodeOperands(
+                  ST1, ST1->getChain(), NewSDVal, ST1->getOperand(2),
+                  ST1->getOperand(3));
+              return CombineTo(ST, SDValue(NewST1, 0));
+            }
+          }
+        } // End ST subset of ST1 case.
       }
     }
   }
 
   // If this is an FP_ROUND or TRUNC followed by a store, fold this into a
   // truncating store.  We can do this even if this is already a truncstore.
   if ((Value.getOpcode() == ISD::FP_ROUND || Value.getOpcode() == ISD::TRUNCATE)
       && Value.getNode()->hasOneUse() && ST->isUnindexed() &&

llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp

if ((BasePtr0.getIndex() == BasePtr1.getIndex() || (IsFI0 != IsFI1) ||
       (IsFI0 || IsGV0 || IsCV0) && (IsFI1 || IsGV1 || IsCV1)) {
     IsAlias = false;
     return true;
   }
   return false; // Cannot determine whether the pointers alias.
 }
 
 bool BaseIndexOffset::contains(int64_t Size, const BaseIndexOffset &Other,
-                               int64_t OtherSize,
-                               const SelectionDAG &DAG) const {
-  int64_t Offset;
+                               int64_t OtherSize, const SelectionDAG &DAG,
+                               int64_t &Offset) const {
   if (!equalBaseIndex(Other, DAG, Offset))
     return false;
   if (Offset >= 0) {
     // Other is after *this:
     // [-------*this---------]
     //            [---Other--]
     // ==Offset==>
     return Offset + OtherSize <= Size;

llvm/test/CodeGen/AArch64/ldst-paired-aliasing.ll

 ; RUN: llc -mcpu cortex-a53 < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-i128:128-n8:16:32:64-S128"
 target triple = "aarch64--linux-gnu"
 
 declare void @f(i8*, i8*)
 declare void @f2(i8*, i8*)
 declare void @_Z5setupv()
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i1) #3
 
 define i32 @main() local_unnamed_addr #1 {
 ; Make sure the stores happen in the correct order (the exact instructions could change).
 ; CHECK-LABEL: main:
 
-; CHECK: str xzr, [sp, #80]
-; CHECK: str w9, [sp, #80]
+; CHECK: orr w9, wzr, #0x1
+; CHECK: str x9, [sp, #80]
 ; CHECK: stp q0, q0, [sp, #48]
 ; CHECK: ldr w8, [sp, #48]
 
 for.body.lr.ph.i.i.i.i.i.i63:
   %b1 = alloca [10 x i32], align 16
   %x0 = bitcast [10 x i32]* %b1 to i8*
   %b2 = alloca [10 x i32], align 16
   %x1 = bitcast [10 x i32]* %b2 to i8*

llvm/test/CodeGen/PowerPC/constant-combines.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=powerpc64-unknown-linux-gnu   -o - %s | FileCheck --check-prefix=BE %s 
 ; RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -o - %s | FileCheck --check-prefix=LE %s
 
 define void @fold_constant_stores_loaddr(i8* %i8_ptr) {
 ; BE-LABEL: fold_constant_stores_loaddr:
 ; BE:       # %bb.0: # %entry
-; BE-NEXT:    li 4, 0
+; BE-NEXT:    li 4, 85
+; BE-NEXT:    sldi 4, 4, 57
 ; BE-NEXT:    std 4, 0(3)
-; BE-NEXT:    li 4, -86
-; BE-NEXT:    stb 4, 0(3)
 ; BE-NEXT:    blr
 ;
 ; LE-LABEL: fold_constant_stores_loaddr:
 ; LE:       # %bb.0: # %entry
-; LE-NEXT:    li 4, 0
-; LE-NEXT:    li 5, -86
+; LE-NEXT:    li 4, 170
 ; LE-NEXT:    std 4, 0(3)
-; LE-NEXT:    stb 5, 0(3)
 ; LE-NEXT:    blr
 entry:
   %i64_ptr = bitcast i8* %i8_ptr to i64*
   store i64   0, i64* %i64_ptr, align 8
   store i8  170,  i8*  %i8_ptr,  align 1
   ret void
 }
 
 
 define void @fold_constant_stores_hiaddr(i8* %i8_ptr) {
 ; BE-LABEL: fold_constant_stores_hiaddr:
 ; BE:       # %bb.0: # %entry
-; BE-NEXT:    li 4, 0
+; BE-NEXT:    li 4, 85
+; BE-NEXT:    sldi 4, 4, 57
 ; BE-NEXT:    std 4, 0(3)
-; BE-NEXT:    li 4, -86
-; BE-NEXT:    stb 4, 0(3)
 ; BE-NEXT:    blr
 ;
 ; LE-LABEL: fold_constant_stores_hiaddr:
 ; LE:       # %bb.0: # %entry
-; LE-NEXT:    li 4, 0
-; LE-NEXT:    li 5, -86
+; LE-NEXT:    li 4, 170
 ; LE-NEXT:    std 4, 0(3)
-; LE-NEXT:    stb 5, 0(3)
 ; LE-NEXT:    blr
 entry:
   %i64_ptr = bitcast i8* %i8_ptr to i64*
   store i64   0, i64* %i64_ptr, align 8
   %i8_ptr2 = getelementptr inbounds i8, i8* %i8_ptr, i64 7
   store i8  170,  i8*  %i8_ptr,  align 1
   ret void
 }

llvm/test/CodeGen/X86/stores-merging.ll

; CHECK-NEXT:    retq
   store i32 456, i32* getelementptr inbounds (%structTy, %structTy* @e, i64 0, i32 2), align 4
   ret void
 }
 
 ;; This variant tests PR25154.
 define void @redundant_stores_merging_reverse() {
 ; CHECK-LABEL: redundant_stores_merging_reverse:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    movabsq $528280977409, %rax # imm = 0x7B00000001
+; CHECK-NEXT:    movabsq $1958505086977, %rax # imm = 0x1C800000001
 ; CHECK-NEXT:    movq %rax, e+{{.*}}(%rip)
-; CHECK-NEXT:    movl $456, e+{{.*}}(%rip) # imm = 0x1C8
 ; CHECK-NEXT:    retq
   store i32 123, i32* getelementptr inbounds (%structTy, %structTy* @e, i64 0, i32 2), align 4
   store i32 456, i32* getelementptr inbounds (%structTy, %structTy* @e, i64 0, i32 2), align 4
   store i32 1, i32* getelementptr inbounds (%structTy, %structTy* @e, i64 0, i32 1), align 4
   ret void
 }
 
 @b = common global [8 x i8] zeroinitializer, align 2