[DAGCombine] Enable more pre-indexed stores

[samparker]

Summary

The DAG combiner previously would not produce a pre-indexed store if the base pointer was a predecessor of the value being stored, so to prevent a cycle in the DAG. However, we could produce a pre-inc store if the store is final use of base pointer.

[efriedma]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12644

This needs a better comment explaining exactly what cases this is rejecting, and which cases it is accepting. (I'm not sure I follow the logic here. What cases need to be rejected for correctness? Are there cases which could be transformed, but shouldn't be transformed to avoid register copies?)

I'm a bit concerned about performance here. isPredecessorOf is expensive.

[samparker]

Hi Eli,

I've added more tests and a few comments.

Yes, predecessor checks are expensive, how about adding an upper limit of uses and/or performing this check under a target flag?

[efriedma]

hasPredecessorHelper supports a limit, that would be fine, probably. (The check is probably fast enough in practice in common cases, so it should be fine as long as it doesn't explode quadratically in extreme cases.)

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12664

Could you clarify what "last use" means? It's not obvious when you're dealing with a DAG. I guess it means the store must be scheduled after every other use of BasePtr?

12666

I think this could still use a bit more clarification...

There are two different uses of ReplaceAllUsesOfValueWith which could cause a cycle related to stored value: the replacement of Ptr with the pre-indexed result, and the rewritten arithmetic relative to BasePtr in OtherUses. Are you trying to prevent both those cycles? Could we be more aggressive if we separated those checks?

12669

The equality check here seems suspect; what if Val is a use of one of the direct users of BasePtr?

[samparker]

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12664

Yes, scheduled last is what I mean.

12666

So yes, I am trying to make sure that Ptr can be replaced legally and I have assumed that by allowing the last scheduled user to be a pre-indexed store, we don't have to worry about OtherUses. Though I am now confused after re-reading statement (3) from above which appears to directly contradict my thoughts.

12669

Hmm. Would it be valid to create an ADD/SUB node and check whether it becomes a predecessor of Val...?

[efriedma]

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks. Is all this extra code really necessary?

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

12666

There's a hasPredecessorHelper call later; I think that handles cases like (3).

12669

ADD/SUB of what, exactly?

More generally, we want to avoid performing predecessor checking more than once, since it's expensive.

[efriedma]

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks.

Err, nevermind, that doesn't do anything; please ignore.

[efriedma]

In D56719#1362292, @efriedma wrote:

I just did a very brief experiment, and just checking if (Val == BasePtr || Val == Ptr || Ptr->isPredecessorOf(Val.getNode())) seems to do the right thing without any additional checks.

Err, nevermind, that doesn't do anything; please ignore.

Hmm... actually, I'm just confusing myself. My suggestion appears to fix your pre_inc_str_multi without causing any regressions (although I haven't run anything outside the regression tests). I'm assuming that's the primary case you're interested in?

[samparker]

Thanks for your suggestion Eli, that works for me.

[efriedma]

LGTM

lib/CodeGen/SelectionDAG/DAGCombiner.cpp

   if (isNullConstant(Offset))
     return false;
 
   // Try turning it into a pre-indexed load / store except when:
   // 1) The new base ptr is a frame index.
   // 2) If N is a store and the new base ptr is either the same as or is a
   //    predecessor of the value being stored.
   // 3) Another use of old base ptr is a predecessor of N. If ptr is folded
   //    that would create a cycle.
   // 4) All uses are load / store ops that use it as old base ptr.
 
   // Check #1.  Preinc'ing a frame index would require copying the stack pointer
   // (plus the implicit offset) to a register to preinc anyway.
   if (isa<FrameIndexSDNode>(BasePtr) || isa<RegisterSDNode>(BasePtr))
     return false;
 
   // Check #2.
   if (!isLoad) {
     SDValue Val = cast<StoreSDNode>(N)->getValue();
-    if (Val == BasePtr || BasePtr.getNode()->isPredecessorOf(Val.getNode()))
+
+    // Would require a copy.
+    if (Val == BasePtr)
+      return false;
+
+    // Would create a cycle.
+    if (Val == Ptr || Ptr->isPredecessorOf(Val.getNode()))
       return false;
   }
 
   // Caches for hasPredecessorHelper.
   SmallPtrSet<const SDNode *, 32> Visited;
   SmallVector<const SDNode *, 16> Worklist;
   Worklist.push_back(N);
 
   // If the offset is a constant, there may be other adds of constants that
   // can be folded with this one. We should do this to avoid having to keep
   // a copy of the original base pointer.
   SmallVector<SDNode *, 16> OtherUses;
   if (isa<ConstantSDNode>(Offset))
     for (SDNode::use_iterator UI = BasePtr.getNode()->use_begin(),
                               UE = BasePtr.getNode()->use_end();
          UI != UE; ++UI) {

test/CodeGen/ARM/indexed-mem.ll

+; RUN: llc -mtriple=thumbv8m.main %s -o - | FileCheck %s --check-prefix=CHECK --check-prefix=CHECK-V8M
+; RUN: llc -mtriple=armv8 %s -o - | FileCheck %s --check-prefix=CHECK-V8
+
+; CHECK-LABEL: pre_inc_ldr
+; CHECK: ldr{{.*}}, [r0, #4]!
+define i32* @pre_inc_ldr(i32* %base, i32 %a) {
+  %addr = getelementptr i32, i32* %base, i32 1
+  %ld = load i32, i32* %addr
+  %addr.1 = getelementptr i32, i32* %base, i32 2
+  %res = add i32 %ld, %a
+  store i32 %res, i32* %addr.1
+  ret i32* %addr
+}
+
+; CHECK-LABEL: pre_dec_ldr
+; CHECK: ldr{{.*}}, [r0, #-4]!
+define i32* @pre_dec_ldr(i32* %base, i32 %a) {
+  %addr = getelementptr i32, i32* %base, i32 -1
+  %ld = load i32, i32* %addr
+  %addr.1 = getelementptr i32, i32* %base, i32 2
+  %res = add i32 %ld, %a
+  store i32 %res, i32* %addr.1
+  ret i32* %addr
+}
+
+; CHECK-LABEL: post_inc_ldr
+; CHECK: ldr{{.*}}, [r0], #4
+define i32* @post_inc_ldr(i32* %base, i32* %addr.2, i32 %a) {
+  %addr = getelementptr i32, i32* %base, i32 0
+  %ld = load i32, i32* %addr
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %res = add i32 %ld, %a
+  store i32 %res, i32* %addr.2
+  ret i32* %addr.1
+}
+
+; CHECK-LABEL: post_dec_ldr
+; CHECK: ldr{{.*}}, [r0], #-4
+define i32* @post_dec_ldr(i32* %base, i32* %addr.2, i32 %a) {
+  %addr = getelementptr i32, i32* %base, i32 0
+  %ld = load i32, i32* %addr
+  %addr.1 = getelementptr i32, i32* %base, i32 -1
+  %res = add i32 %ld, %a
+  store i32 %res, i32* %addr.2
+  ret i32* %addr.1
+}
+
+; CHECK-LABEL: pre_inc_str
+; CHECK: str{{.*}}, [r0, #4]!
+define i32* @pre_inc_str(i32* %base, i32 %a, i32 %b) {
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %res = add i32 %a, %b
+  store i32 %res, i32* %addr.1
+  ret i32* %addr.1
+}
+
+; CHECK-LABEL: pre_dec_str
+; CHECK: str{{.*}}, [r0, #-4]!
+define i32* @pre_dec_str(i32* %base, i32 %a, i32 %b) {
+  %res = add i32 %a, %b
+  %addr.1 = getelementptr i32, i32* %base, i32 -1
+  store i32 %res, i32* %addr.1
+  ret i32* %addr.1
+}
+
+; CHECK-LABEL: post_inc_str
+; CHECK: str{{.*}}, [r0], #4
+define i32* @post_inc_str(i32* %base, i32 %a, i32 %b) {
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %res = add i32 %a, %b
+  store i32 %res, i32* %base
+  ret i32* %addr.1
+}
+
+; CHECK-LABEL: post_dec_str
+; CHECK: str{{.*}}, [r0], #-4
+define i32* @post_dec_str(i32* %base, i32 %a, i32 %b) {
+  %addr.1 = getelementptr i32, i32* %base, i32 -1
+  %res = add i32 %a, %b
+  store i32 %res, i32* %base
+  ret i32* %addr.1
+}
+
+; TODO: Generate ldrd
+; CHECK-LABEL: pre_inc_ldrd
+; CHECK: ldr{{.*}}, #4]!
+define i32* @pre_inc_ldrd(i32* %base) {
+  %addr = getelementptr i32, i32* %base, i32 1
+  %addr.1 = getelementptr i32, i32* %base, i32 2
+  %addr.2 = getelementptr i32, i32* %base, i32 3
+  %ld = load i32, i32* %addr
+  %ld.1 = load i32, i32* %addr.1
+  %res = add i32 %ld, %ld.1
+  store i32 %res, i32* %addr.2
+  ret i32* %addr
+}
+
+; TODO: Generate ldrd
+; CHECK-LABEL: pre_dec_ldrd
+; CHECK: ldr{{.*}}, #-4]!
+define i32* @pre_dec_ldrd(i32* %base) {
+  %addr = getelementptr i32, i32* %base, i32 -1
+  %addr.1 = getelementptr i32, i32* %base, i32 -2
+  %addr.2 = getelementptr i32, i32* %base, i32 -3
+  %ld = load i32, i32* %addr
+  %ld.1 = load i32, i32* %addr.1
+  %res = add i32 %ld, %ld.1
+  store i32 %res, i32* %addr.2
+  ret i32* %addr
+}
+
+; TODO: Generate post inc
+; CHECK-LABEL: post_inc_ldrd
+; CHECK-V8M: ldrd{{.*}}, [r0]
+; CHECK-V8: ldm
+; CHECK: add{{.*}}, #8
+define i32* @post_inc_ldrd(i32* %base, i32* %addr.3) {
+  %addr = getelementptr i32, i32* %base, i32 0
+  %ld = load i32, i32* %addr
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %ld.1 = load i32, i32* %addr.1
+  %addr.2 = getelementptr i32, i32* %base, i32 2
+  %res = add i32 %ld, %ld.1
+  store i32 %res, i32* %addr.3
+  ret i32* %addr.2
+}
+
+; CHECK-LABEL: pre_inc_str_multi
+; CHECK: str{{.*}}, #8]!
+define i32* @pre_inc_str_multi(i32* %base) {
+  %addr = getelementptr i32, i32* %base, i32 0
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %ld = load i32, i32* %addr
+  %ld.1 = load i32, i32* %addr.1
+  %res = add i32 %ld, %ld.1
+  %addr.2 = getelementptr i32, i32* %base, i32 2
+  store i32 %res, i32* %addr.2
+  ret i32* %addr.2
+}
+
+; CHECK-LABEL: pre_dec_str_multi
+; CHECK: str{{.*}}, #-4]!
+define i32* @pre_dec_str_multi(i32* %base) {
+  %addr = getelementptr i32, i32* %base, i32 0
+  %addr.1 = getelementptr i32, i32* %base, i32 1
+  %ld = load i32, i32* %addr
+  %ld.1 = load i32, i32* %addr.1
+  %res = add i32 %ld, %ld.1
+  %addr.2 = getelementptr i32, i32* %base, i32 -1
+  store i32 %res, i32* %addr.2
+  ret i32* %addr.2
+}
+
+; CHECK-LABEL: illegal_pre_inc_store_1
+; CHECK-NOT: str{{.*}} ]!
+define i32* @illegal_pre_inc_store_1(i32* %base) {
+entry:
+  %ptr.to.use = getelementptr i32, i32* %base, i32 2
+  %ptr.to.store = ptrtoint i32* %base to i32
+  store i32 %ptr.to.store, i32* %ptr.to.use, align 4
+  ret i32* %ptr.to.use
+}
+
+; TODO: The mov should be unecessary
+; CHECK-LABEL: legal_pre_inc_store_needs_copy_1
+; CHECK: add{{.*}}, #8
+; CHECK-NOT: str{{.*}}]!
+; CHECK: mov
+define i32* @legal_pre_inc_store_needs_copy_1(i32* %base) {
+entry:
+  %ptr.to.use = getelementptr i32, i32* %base, i32 2
+  %ptr.to.store = ptrtoint i32* %ptr.to.use to i32
+  store i32 %ptr.to.store, i32* %ptr.to.use, align 4
+  ret i32* %ptr.to.use
+}
+
+; CHECK-LABEL: legal_pre_inc_store_needs_copy_2
+; CHECK-NOT: mov
+; CHECK-NOT: str{{.*}}]!
+define i32* @legal_pre_inc_store_needs_copy_2(i32 %base) {
+entry:
+  %ptr = inttoptr i32 %base to i32*
+  %ptr.to.use = getelementptr i32, i32* %ptr, i32 2
+  store i32 %base, i32* %ptr.to.use, align 4
+  ret i32* %ptr.to.use
+}