[ARM] Fix insert point for store rescheduling.

[efriedma]

Summary

In ARMPreAllocLoadStoreOpt::RescheduleOps, LastOp should be the last operation which we want to merge. If we break out of the loop because an operation has the wrong offset, we shouldn't use that operation as LastOp.

This patch fixes some cases where we would move stores to the wrong insert point.

Now amended with fix to increment NumMove in the right place.

[rengolin]

Hi Eli,

Looks trivial, but would be better to have a target feature for this.

Also, would be better with an additional test where that threshold is crossed and we don't re-schedule the stores.

cheers,
--renato

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

2180

I assume this would depend on sub-architecture, so better to have a target feature, even if it's the same value for all by default, this would allow much easier fiddling and changes in the future.

[efriedma]

would be better to have a target feature for this.

A target feature for what, exactly? This fix doesn't add any new tunable parameters. (I can add some target features for ARMPreAllocLoadStoreOpt in general in a followup.)

[MatzeB]

I should probably write a tutorial/blogpost about that; a good .mir test should be minimal and not just an llc -stop-after= dump, here's how to get there:

• IR can be removed in most cases. Backreferences to IR happen with blocknames like bb.N.xxx where xxx is the IR block name can be replaced with bb.N. Memory operands keep reference to IR like (store 4 into %irvalue) they can usually be changed to (store 4) because the test doesn't need detail memory disambiguation.
• Most yaml statements can be removed (the whole frameInfo: block here, alignment, returnsTwice, legalized, regBankSelected, selected probably)
• There is a new feature to define the register of a vreg when writing to it: body: %0 : gpr = COPY ... instead of registers: - { id: 0, class: gpr } body: %0 = COPY ...

[MatzeB]

The change itself looks straightforward.
Having the magic number 8 tunable would indeed be nice, unfortunately target features are only boolean (enable or disabled) today; While I would applaud everyone improving the targetfeature system to support arbitrary integer values, I don't think we need to block this bugfix for it esp. since the magic number already existed in the code.

[rengolin]

In D30124#682714, @MatzeB wrote:

The change itself looks straightforward.
Having the magic number 8 tunable would indeed be nice, unfortunately target features are only boolean (enable or disabled) today; While I would applaud everyone improving the targetfeature system to support arbitrary integer values, I don't think we need to block this bugfix for it esp. since the magic number already existed in the code.

We already have integer values attributed to sub-architectures. But I'm not fussed about this in particular, just thought it would be a good and easy place to already fix the fixme.

[MatzeB]

In D30124#682728, @rengolin wrote:

In D30124#682714, @MatzeB wrote:

The change itself looks straightforward.
Having the magic number 8 tunable would indeed be nice, unfortunately target features are only boolean (enable or disabled) today; While I would applaud everyone improving the targetfeature system to support arbitrary integer values, I don't think we need to block this bugfix for it esp. since the magic number already existed in the code.

We already have integer values attributed to sub-architectures. But I'm not fussed about this in particular, just thought it would be a good and easy place to already fix the fixme.

Ok, true. ARMSubTarget::initSubtargetFeatures() can set arbitrary values depend on the selected architecture, this may actually be useful here. What I wanted to say is that the subtarget feature APIs/tablegen do not allow you to do something like llc -mattr=MyLimit=8 yet.

[rengolin]

In D30124#682736, @MatzeB wrote:

What I wanted to say is that the subtarget feature APIs/tablegen do not allow you to do something like llc -mattr=MyLimit=8 yet.

Right, I'm not sure we want this at all, ever, for this particular choice.

I'm not even sure we need different values, but since we should be moving magic numbers to descriptive constants, there seems like a better place than most to put it, even if all targets use the same.

[efriedma]

Reverted in r296718.

[efriedma]

Updated patch. Move the increment of NumMove after the if statement, so we move the correct number of stores. (Hopefully I'm not making any other silly mistakes.)

[efriedma]

Correctly use FileCheck in new test.

[rengolin]

Let's try again. :)

lib/Target/ARM/ARMLoadStoreOptimizer.cpp

while (Ops.size() > 1) {
     unsigned LastLoc = 0;
     MachineInstr *FirstOp = nullptr;
     MachineInstr *LastOp = nullptr;
     int LastOffset = 0;
     unsigned LastOpcode = 0;
     unsigned LastBytes = 0;
     unsigned NumMove = 0;
     for (int i = Ops.size() - 1; i >= 0; --i) {
+      // Make sure each operation has the same kind.
       MachineInstr *Op = Ops[i];
-      unsigned Loc = MI2LocMap[Op];
-      if (Loc <= FirstLoc) {
-        FirstLoc = Loc;
-        FirstOp = Op;
-      }
-      if (Loc >= LastLoc) {
-        LastLoc = Loc;
-        LastOp = Op;
-      }
-
       unsigned LSMOpcode
         = getLoadStoreMultipleOpcode(Op->getOpcode(), ARM_AM::ia);
       if (LastOpcode && LSMOpcode != LastOpcode)
         break;
 
+      // Check that we have a continuous set of offsets.
       int Offset = getMemoryOpOffset(*Op);
       unsigned Bytes = getLSMultipleTransferSize(Op);
       if (LastBytes) {
         if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes))
           break;
       }
+
+      // Don't try to reschedule too many instructions.
+      if (NumMove == 8) // FIXME: Tune this limit.
+        break;
+
+      // Found a mergable instruction; save information about it.
+      ++NumMove;
       LastOffset = Offset;
       LastBytes = Bytes;
       LastOpcode = LSMOpcode;
-      if (++NumMove == 8) // FIXME: Tune this limit.
-        break;
+
+      unsigned Loc = MI2LocMap[Op];
+      if (Loc <= FirstLoc) {
+        FirstLoc = Loc;
+        FirstOp = Op;
+      }
+      if (Loc >= LastLoc) {
+        LastLoc = Loc;
+        LastOp = Op;
+      }
     }
 
     if (NumMove <= 1)
       Ops.pop_back();
     else {
       SmallPtrSet<MachineInstr*, 4> MemOps;
       SmallSet<unsigned, 4> MemRegs;
       for (size_t i = Ops.size() - NumMove, e = Ops.size(); i != e; ++i) {

test/CodeGen/ARM/ldm-stm-i256.ll

+; RUN: llc -mtriple=armv7--eabi -verify-machineinstrs < %s
+
+; Check the way we schedule/merge a bunch of loads and stores.
+; Originally test/CodeGen/ARM/2011-07-07-ScheduleDAGCrash.ll ; now
+; being used as a test of optimizations related to ldm/stm.
+
+; FIXME: We could merge more loads/stores with regalloc hints.
+; FIXME: Fix scheduling so we don't have 16 live registers.
+
+define void @f(i256* nocapture %a, i256* nocapture %b, i256* nocapture %cc, i256* nocapture %dd) nounwind uwtable noinline ssp {
+entry:
+  %c = load i256, i256* %cc
+  %d = load i256, i256* %dd
+  %add = add nsw i256 %c, %d
+  store i256 %add, i256* %a, align 8
+  %or = or i256 %c, 1606938044258990275541962092341162602522202993782792835301376
+  %add6 = add nsw i256 %or, %d
+  store i256 %add6, i256* %b, align 8
+  ret void
+  ; CHECK-DAG: ldm r3
+  ; CHECK-DAG: ldm r2
+  ; CHECK-DAG: ldr {{,*}}, [r3, #20]
+  ; CHECK-DAG: ldr {{,*}}, [r3, #16]
+  ; CHECK-DAG: ldr {{,*}}, [r3, #28]
+  ; CHECK-DAG: ldr {{,*}}, [r3, #24]
+  ; CHECK-DAG: ldr {{,*}}, [r2, #20]
+  ; CHECK-DAG: ldr {{,*}}, [r2, #16]
+  ; CHECK-DAG: ldr {{,*}}, [r2, #28]
+  ; CHECK-DAG: ldr {{,*}}, [r2, #24]
+  ; CHECK-DAG: stmib r0
+  ; CHECK-DAG: str {{.*}}, [r0]
+  ; CHECK-DAG: str {{.*}}, [r0, #24]
+  ; CHECK-DAG: str {{.*}}, [r0, #28]
+  ; CHECK-DAG: str {{.*}}, [r1]
+  ; CHECK-DAG: stmib r1
+  ; CHECK-DAG: str {{.*}}, [r1, #24]
+  ; CHECK-DAG: str {{.*}}, [r1, #28]
+}

test/CodeGen/ARM/prera-ldst-insertpt.mir

bb.0.entry:
     %3 : rgpr = t2MUL %2, %2, 14, _
     %4 : rgpr = t2MUL %1, %1, 14, _
     %5 : rgpr = t2MOVi32imm -858993459
     %6 : rgpr, %7 : rgpr  = t2UMULL killed %3, %5, 14, _
     %8 : rgpr, %9 : rgpr  = t2UMULL killed %4, %5, 14, _
     t2STRi12 %1, %0, 0, 14, _ :: (store 4)
     %10 : rgpr = t2LSLri %2, 1, 14, _, _
     t2STRi12 killed %10, %0, 4, 14, _ :: (store 4)
+
+    ; Make sure we move the paired stores next to each other, and
+    ; insert them in an appropriate location.
+    ; CHECK: t2STRi12 %1,
+    ; CHECK-NEXT: t2STRi12 killed %10,
+    ; CHECK-NEXT: t2MOVi
+    ; CHECK-NEXT: t2ADDrs
+
     %11 : rgpr = t2MOVi 55, 14, _, _
     %12 : gprnopc = t2ADDrs %11, killed %7, 19, 14, _, _
     t2STRi12 killed %12, %0, 16, 14, _ :: (store 4)
     %13 : gprnopc = t2ADDrs %11, killed %9, 19, 14, _, _
     t2STRi12 killed %13, %0, 20, 14, _ :: (store 4)
 
     ; Make sure we move the paired stores next to each other.
-    ; FIXME: Make sure we don't extend the live-range of a store
-    ; when we don't need to.
-    ; CHECK: t2STRi12 %1,
-    ; CHECK-NEXT: t2STRi12 killed %10,
-    ; CHECK-NEXT: %13 = t2ADDrs %11
-    ; CHECK-NEXT: t2STRi12 killed %12,
+    ; CHECK: t2STRi12 killed %12,
     ; CHECK-NEXT: t2STRi12 killed %13,
 
     tBX_RET 14, _
 ---
 # CHECK-LABEL: name: b
 name:            b
 alignment:       1
 tracksRegLiveness: true
 liveins:
   - { reg: '%r0', virtual-reg: '%0' }
   - { reg: '%r1', virtual-reg: '%1' }
   - { reg: '%r2', virtual-reg: '%2' }
 body:             |
   bb.0.entry:
     liveins: %r0, %r1, %r2
 
     %2 : rgpr = COPY %r2
     %1 : rgpr = COPY %r1
     %0 : gpr = COPY %r0
     t2STRi12 %1, %0, 0, 14, _ :: (store 4)
     %10 : rgpr = t2LSLri %2, 1, 14, _, _
     t2STRi12 killed %10, %0, 4, 14, _ :: (store 4)
     %3 : rgpr = t2MUL %2, %2, 14, _
     t2STRi12 %3, %0, 8, 14, _ :: (store 4)
+
+    ; Make sure we move the paired stores next to each other, and
+    ; insert them in an appropriate location.
+    ; CHECK: t2STRi12 {{.*}}, 0
+    ; CHECK-NEXT: t2STRi12 {{.*}}, 4
+    ; CHECK-NEXT: t2STRi12 {{.*}}, 8
+    ; CHECK-NEXT: t2MUL
+    ; CHECK-NEXT: t2MOVi32imm
+
     %4 : rgpr = t2MUL %1, %1, 14, _
     %5 : rgpr = t2MOVi32imm -858993459
     %6 : rgpr, %7 : rgpr  = t2UMULL killed %3, %5, 14, _
     %8 : rgpr, %9 : rgpr  = t2UMULL killed %4, %5, 14, _
     %10 : rgpr = t2LSLri %2, 1, 14, _, _
     %11 : rgpr = t2MOVi 55, 14, _, _
     %12 : gprnopc = t2ADDrs %11, killed %7, 19, 14, _, _
     t2STRi12 killed %12, %0, 16, 14, _ :: (store 4)
     %13 : gprnopc = t2ADDrs %11, killed %9, 19, 14, _, _
     t2STRi12 killed %13, %0, 20, 14, _ :: (store 4)
 
     ; Make sure we move the paired stores next to each other.
-    ; FIXME: Make sure we don't extend the live-range of a store
-    ; when we don't need to.
-    ; CHECK: t2STRi12 {{.*}}, 0
-    ; CHECK-NEXT: t2STRi12 {{.*}}, 4
-    ; CHECK-NEXT: t2STRi12 {{.*}}, 8
-    ; CHECK-NEXT: t2ADDrs
-    ; CHECK-NEXT: t2STRi12 {{.*}}, 16
+    ; CHECK: t2STRi12 {{.*}}, 16
     ; CHECK-NEXT: t2STRi12 {{.*}}, 20
 
     tBX_RET 14, _
 
 ...