[DAGCombine] Skip PostInc combine with later users

[samparker]

Summary

When decided whether to generate a post-inc load/store, look at the other memory nodes that use the same base address and, if any proceed the current node, then don't do the combine.
The change only seems to be affecting the Arm backend, which I was surprised at, but it appears to fix a lot of our issues around MVE masked load/stores having to store a temporary address after an early post-increment on a shared base address.

[dmgreen]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14189

Should we also be checking that this Use can use some addressing mode and fold the offset in? Not that it just is a memory operation?

14192

Do we need to store LaterMemOps or can we just set TryNext to true?

[samparker]

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

14189

Yeah, I shouldn't have been lazy.

[samparker]

Rebased and exit if a later post-inc/dec use is found.

[dmgreen]

Looks nice.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

       // 2) Op must be independent of N, i.e. Op is neither a predecessor
       //    nor a successor of N. Otherwise, if Op is folded that would
       //    create a cycle.
 
       if (isa<FrameIndexSDNode>(BasePtr) || isa<RegisterSDNode>(BasePtr))
         continue;
 
       // Check for #1.
+      SmallPtrSet<MemSDNode*, 4> LaterMemOps;
+      SmallVector<const SDNode *, 8> Worklist;
+      SmallPtrSet<const SDNode *, 32> Visited;
       bool TryNext = false;
       for (SDNode *Use : BasePtr.getNode()->uses()) {
         if (Use == Ptr.getNode())
           continue;
 
+        // Record other memory accesses users of this base, and record any
+        // which proceed N. We can then try not to combine into post-inc when
+        // there are later users which could do it instead.
+        if (isa<MemSDNode>(Use)) {
+          Worklist.push_back(Use);
+          if (SDNode::hasPredecessorHelper(N, Visited, Worklist)) {
+            LaterMemOps.insert(cast<MemSDNode>(Use));
+            break;
+          }
+        }
+
         // If all the uses are load / store addresses, then don't do the
         // transformation.
-        if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB) {
-          bool RealUse = false;
-          for (SDNode *UseUse : Use->uses()) {
-            if (!canFoldInAddressingMode(Use, UseUse, DAG, TLI))
-              RealUse = true;
-          }
+        if (Use->getOpcode() != ISD::ADD && Use->getOpcode() != ISD::SUB)
+          continue;
 
-          if (!RealUse) {
-            TryNext = true;
+        bool RealUse = false;
+        for (SDNode *UseUse : Use->uses()) {
+          if (!canFoldInAddressingMode(Use, UseUse, DAG, TLI)) {
+            RealUse = true;
             break;
           }
         }
+
+        if (!RealUse) {
+          TryNext = true;
+          break;
+        }
       }
 
-      if (TryNext)
+      if (TryNext || !LaterMemOps.empty())
         continue;
 
       // Check for #2.
-      SmallPtrSet<const SDNode *, 32> Visited;
-      SmallVector<const SDNode *, 8> Worklist;
+      Worklist.clear();
+      Visited.clear();
       // Ptr is predecessor to both N and Op.
       Visited.insert(Ptr.getNode());
       Worklist.push_back(N);
       Worklist.push_back(Op);
       if (!SDNode::hasPredecessorHelper(N, Visited, Worklist) &&
           !SDNode::hasPredecessorHelper(Op, Visited, Worklist)) {
         SDValue Result;
         if (!IsMasked)

llvm/test/CodeGen/Thumb/frame-access.ll

 ; CHECK:      sub sp, #36
 ; Setup BP
 ; CHECK:      mov r6, sp
 ; Outoging arguments
 ; CHECK:      sub sp, #508
 ; CHECK-NEXT: sub sp, #508
 ; CHECK-NEXT: sub sp, #8
 ; Argument addresses computed relative to BP
-; CHECK:      adds r0, r6, #7
-; CHECK-NEXT: adds r0, #13
+; CHECK:      adds r4, r6, #7
+; CHECK-NEXT: adds r4, #13
 ; CHECK:      adds r1, r6, #7
 ; CHECK-NEXT: adds r1, #9
 ; CHECK:      adds r5, r6, #7
 ; CHECK-NEXT: adds r5, #5
 ; CHECK:      bl   u
 ; Stack restored before next call
 ; CHECK:      add  sp, #508
 ; CHECK-NEXT: add  sp, #508
 ; CHECK-NEXT: add  sp, #8
 ; CHECK:      bl   u

llvm/test/CodeGen/Thumb2/LowOverheadLoops/cond-vector-reduce-mve-codegen.ll

 
 define dso_local void @continue_on_zero(i32* noalias nocapture %arg, i32* noalias nocapture readonly %arg1, i32 %arg2) {
 ; CHECK-LABEL: continue_on_zero:
 ; CHECK:       @ %bb.0: @ %bb
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
-; CHECK-NEXT:    mov r3, r0
 ; CHECK-NEXT:    dlstp.32 lr, r2
 ; CHECK-NEXT:  .LBB4_1: @ %bb9
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    vldrw.u32 q0, [r1], #16
 ; CHECK-NEXT:    vcmp.i32 ne, q0, zr
 ; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vldrwt.u32 q1, [r3], #16
+; CHECK-NEXT:    vldrwt.u32 q1, [r0]
 ; CHECK-NEXT:    vmul.i32 q0, q1, q0
 ; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vstrwt.32 q0, [r0]
-; CHECK-NEXT:    mov r0, r3
+; CHECK-NEXT:    vstrwt.32 q0, [r0], #16
 ; CHECK-NEXT:    letp lr, .LBB4_1
 ; CHECK-NEXT:  @ %bb.2: @ %bb27
 ; CHECK-NEXT:    pop {r7, pc}
 bb:
   %tmp = icmp eq i32 %arg2, 0
   br i1 %tmp, label %bb27, label %bb3
 
 bb3:                                              ; preds = %bb

 ; CHECK-NEXT:    cmp r3, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
 ; CHECK-NEXT:    add.w r12, r3, #3
 ; CHECK-NEXT:    mov.w lr, #1
 ; CHECK-NEXT:    bic r12, r12, #3
 ; CHECK-NEXT:    sub.w r12, r12, #4
 ; CHECK-NEXT:    add.w lr, lr, r12, lsr #2
-; CHECK-NEXT:    mov r12, r0
 ; CHECK-NEXT:    dls lr, lr
 ; CHECK-NEXT:  .LBB5_1: @ %bb12
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
 ; CHECK-NEXT:    vctp.32 r3
 ; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vldrwt.u32 q0, [r12], #16
+; CHECK-NEXT:    vldrwt.u32 q0, [r0]
 ; CHECK-NEXT:    vpttt.i32 ne, q0, zr
 ; CHECK-NEXT:    vcmpt.s32 le, q0, r2
 ; CHECK-NEXT:    vctpt.32 r3
 ; CHECK-NEXT:    vldrwt.u32 q1, [r1], #16
 ; CHECK-NEXT:    subs r3, #4
 ; CHECK-NEXT:    vmul.i32 q0, q1, q0
 ; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vstrwt.32 q0, [r0]
-; CHECK-NEXT:    mov r0, r12
+; CHECK-NEXT:    vstrwt.32 q0, [r0], #16
 ; CHECK-NEXT:    le lr, .LBB5_1
 ; CHECK-NEXT:  @ %bb.2: @ %bb32
 ; CHECK-NEXT:    pop {r7, pc}
 bb:
   %tmp = icmp eq i32 %arg3, 0
   br i1 %tmp, label %bb32, label %bb4
 
 bb4:                                              ; preds = %bb

llvm/test/CodeGen/Thumb2/LowOverheadLoops/extending-loads.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=thumbv8.1m.main -mattr=+mve -disable-mve-tail-predication=false %s -o - | FileCheck %s
 
 define dso_local arm_aapcs_vfpcc void @sext_i8(i16* noalias nocapture %a, i8* nocapture readonly %b, i32 %N) {
 ; CHECK-LABEL: sext_i8:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
-; CHECK-NEXT:    mov r3, r0
 ; CHECK-NEXT:    dlstp.16 lr, r2
-; CHECK:    .LBB0_1: @ %vector.body
-; CHECK:       vldrb.s16 q0, [r1], #8
-; CHECK-NEXT:    vldrh.u16 q1, [r3], #16
+; CHECK-NEXT:  .LBB0_1: @ %vector.body
+; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    vldrb.s16 q0, [r1], #8
+; CHECK-NEXT:    vldrh.u16 q1, [r0]
 ; CHECK-NEXT:    vadd.i16 q0, q1, q0
-; CHECK-NEXT:    vstrh.16 q0, [r0]
-; CHECK-NEXT:    mov r0, r3
+; CHECK-NEXT:    vstrh.16 q0, [r0], #16
 ; CHECK-NEXT:    letp lr, .LBB0_1
 ; CHECK-NEXT:  @ %bb.2: @ %for.cond.cleanup
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %cmp8 = icmp eq i32 %N, 0
   br i1 %cmp8, label %for.cond.cleanup, label %vector.ph
 
 vector.ph:                                        ; preds = %entry

 ; Function Attrs: nofree norecurse nounwind
 define dso_local arm_aapcs_vfpcc void @zext_i8(i16* noalias nocapture %a, i8* nocapture readonly %b, i32 %N) local_unnamed_addr #0 {
 ; CHECK-LABEL: zext_i8:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
-; CHECK-NEXT:    mov r3, r0
 ; CHECK-NEXT:    dlstp.16 lr, r2
-; CHECK:    .LBB1_1: @ %vector.body
-; CHECK:       vldrb.u16 q0, [r1], #8
-; CHECK-NEXT:    vldrh.u16 q1, [r3], #16
+; CHECK-NEXT:  .LBB1_1: @ %vector.body
+; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    vldrb.u16 q0, [r1], #8
+; CHECK-NEXT:    vldrh.u16 q1, [r0]
 ; CHECK-NEXT:    vadd.i16 q0, q1, q0
-; CHECK-NEXT:    vstrh.16 q0, [r0]
-; CHECK-NEXT:    mov r0, r3
+; CHECK-NEXT:    vstrh.16 q0, [r0], #16
 ; CHECK-NEXT:    letp lr, .LBB1_1
 ; CHECK-NEXT:  @ %bb.2: @ %for.cond.cleanup
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %cmp8 = icmp eq i32 %N, 0
   br i1 %cmp8, label %for.cond.cleanup, label %vector.ph
 
 vector.ph:                                        ; preds = %entry

 ; Function Attrs: nofree norecurse nounwind
 define dso_local arm_aapcs_vfpcc void @sext_i16(i32* noalias nocapture %a, i16* nocapture readonly %b, i32 %N) local_unnamed_addr #0 {
 ; CHECK-LABEL: sext_i16:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
-; CHECK-NEXT:    mov r3, r0
 ; CHECK-NEXT:    dlstp.32 lr, r2
-; CHECK:    .LBB2_1: @ %vector.body
-; CHECK:       vldrh.s32 q0, [r1], #8
-; CHECK-NEXT:    vldrw.u32 q1, [r3], #16
+; CHECK-NEXT:  .LBB2_1: @ %vector.body
+; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    vldrh.s32 q0, [r1], #8
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
 ; CHECK-NEXT:    vadd.i32 q0, q1, q0
-; CHECK-NEXT:    vstrw.32 q0, [r0]
-; CHECK-NEXT:    mov r0, r3
+; CHECK-NEXT:    vstrw.32 q0, [r0], #16
 ; CHECK-NEXT:    letp lr, .LBB2_1
 ; CHECK-NEXT:  @ %bb.2: @ %for.cond.cleanup
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %cmp6 = icmp eq i32 %N, 0
   br i1 %cmp6, label %for.cond.cleanup, label %vector.ph
 
 vector.ph:                                        ; preds = %entry

 ; Function Attrs: nofree norecurse nounwind
 define dso_local arm_aapcs_vfpcc void @zext_i16(i32* noalias nocapture %a, i16* nocapture readonly %b, i32 %N) local_unnamed_addr #0 {
 ; CHECK-LABEL: zext_i16:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    push {r7, lr}
 ; CHECK-NEXT:    cmp r2, #0
 ; CHECK-NEXT:    it eq
 ; CHECK-NEXT:    popeq {r7, pc}
-; CHECK-NEXT:    mov r3, r0
 ; CHECK-NEXT:    dlstp.32 lr, r2
-; CHECK:     .LBB3_1: @ %vector.body
-; CHECK:       vldrh.u32 q0, [r1], #8
-; CHECK-NEXT:    vldrw.u32 q1, [r3], #16
+; CHECK-NEXT:  .LBB3_1: @ %vector.body
+; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
+; CHECK-NEXT:    vldrh.u32 q0, [r1], #8
+; CHECK-NEXT:    vldrw.u32 q1, [r0]
 ; CHECK-NEXT:    vadd.i32 q0, q1, q0
-; CHECK-NEXT:    vstrw.32 q0, [r0]
-; CHECK-NEXT:    mov r0, r3
+; CHECK-NEXT:    vstrw.32 q0, [r0], #16
 ; CHECK-NEXT:    letp lr, .LBB3_1
 ; CHECK-NEXT:  @ %bb.2: @ %for.cond.cleanup
 ; CHECK-NEXT:    pop {r7, pc}
 entry:
   %cmp6 = icmp eq i32 %N, 0
   br i1 %cmp6, label %for.cond.cleanup, label %vector.ph
 
 vector.ph:                                        ; preds = %entry

llvm/test/CodeGen/Thumb2/mve-postinc-lsr.ll

 ; CHECK-NEXT:    cmp r3, #1
 ; CHECK-NEXT:    blt .LBB1_3
 ; CHECK-NEXT:  @ %bb.1: @ %vector.ph
 ; CHECK-NEXT:    add.w r12, r3, #3
 ; CHECK-NEXT:    adr r4, .LCPI1_0
 ; CHECK-NEXT:    bic r12, r12, #3
 ; CHECK-NEXT:    mov.w lr, #1
 ; CHECK-NEXT:    sub.w r12, r12, #4
-; CHECK-NEXT:    subs r3, #1
 ; CHECK-NEXT:    vldrw.u32 q0, [r4]
-; CHECK-NEXT:    vdup.32 q1, r3
 ; CHECK-NEXT:    add.w lr, lr, r12, lsr #2
-; CHECK-NEXT:    mov.w r12, #0
-; CHECK-NEXT:    mov r3, r2
+; CHECK-NEXT:    sub.w r12, r3, #1
+; CHECK-NEXT:    movs r3, #0
+; CHECK-NEXT:    vdup.32 q1, r12
 ; CHECK-NEXT:    dls lr, lr
 ; CHECK-NEXT:  .LBB1_2: @ %vector.body
 ; CHECK-NEXT:    @ =>This Inner Loop Header: Depth=1
-; CHECK-NEXT:    vdup.32 q2, r12
-; CHECK-NEXT:    add.w r12, r12, #4
+; CHECK-NEXT:    vdup.32 q2, r3
+; CHECK-NEXT:    adds r3, #4
 ; CHECK-NEXT:    vorr q2, q2, q0
 ; CHECK-NEXT:    vpttt.u32 cs, q1, q2
 ; CHECK-NEXT:    vldrwt.u32 q2, [r0], #16
 ; CHECK-NEXT:    vldrwt.u32 q3, [r1], #16
-; CHECK-NEXT:    vldrwt.u32 q4, [r3], #16
+; CHECK-NEXT:    vldrwt.u32 q4, [r2]
 ; CHECK-NEXT:    vfma.f32 q4, q3, q2
 ; CHECK-NEXT:    vpst
-; CHECK-NEXT:    vstrwt.32 q4, [r2]
-; CHECK-NEXT:    mov r2, r3
+; CHECK-NEXT:    vstrwt.32 q4, [r2], #16
 ; CHECK-NEXT:    le lr, .LBB1_2
 ; CHECK-NEXT:  .LBB1_3: @ %for.cond.cleanup
 ; CHECK-NEXT:    vpop {d8, d9}
 ; CHECK-NEXT:    pop {r4, pc}
 ; CHECK-NEXT:    .p2align 4
 ; CHECK-NEXT:  @ %bb.4:
 ; CHECK-NEXT:  .LCPI1_0:
 ; CHECK-NEXT:    .long 0 @ 0x0