[AArch64] Enable more load clustering in the MI Scheduler.

[mcrosier]

Summary

This patch adds unscaled loads and sign-extend loads to the TII getMemOpBaseRegImmOfs API, which is used to control clustering in the MI scheduler. This is done to create more opportunities for load pairing. I've also added the scaled LDRSWui instruction, which was missing from the scaled instructions. Finally, I've added support in shouldClusterLoads for clustering adjacent sext and zext loads that too can be paired by the load/store optimizer.

Overall, this patch increases the number of unscaled pairs by about 3% for Spec2006. I saw similar results for Spec2000. Also, I didn't see any serious changes in the register allocator statistics (see below).

Below is a summary of the llvm stats when comparing without and with this patch. For example, the first stat indicates 148 (or ~3.18%) more ldps are generated from unscaled loads and and the total number of paired instructions increase by 317 (or 0.64%).

Summary:

 148 (3.18) aarch64-ldst-opt - Number of load/store from unscaled generated     
 317 (0.64) aarch64-ldst-opt - Number of load/store pair instructions generated 
  10 (0.42) aarch64-ldst-opt - Number of post-index updates folded              
-272 (-0.01) asm-printer - Number of machine instrs printed                      
-936 (-0.00) assembler - Number of emitted object file bytes                     
   6 (0.00) assembler - Number of evaluated fixups                              
   6 (0.00) mccodeemitter - Number of MC fixups created.                        
-272 (-0.01) mccodeemitter - Number of MC instructions emitted.                  
  11 (0.00) mcexpr - Number of MCExpr evaluations                               
  96 (0.00) pei - Number of bytes used for stack in all functions               
   4 (0.00) regalloc - Number of copies inserted for splitting                  
  -1 (-0.00) regalloc - Number of identity moves eliminated after rewriting      
   3 (0.01) regalloc - Number of interferences evicted                          
   2 (0.22) regalloc - Number of live ranges fractured by DCE                   
  15 (0.01) regalloc - Number of new live ranges queued                         
   8 (0.00) regalloc - Number of registers assigned                             
   4 (0.01) regalloc - Number of registers unassigned                           
   1 (0.00) regalloc - Number of rematerialized defs for spilling               
  -1 (-0.03) regalloc - Number of rematerialized defs for splitting              
   2 (0.01) regalloc - Number of spill slots allocated                          
   1 (0.00) regalloc - Number of spilled live ranges                            
   5 (0.04) regalloc - Number of split global live ranges                       
  -2 (-0.10) regalloc - Number of split local live ranges                        
   2 (0.01) regalloc - Number of splits finished                                
   2 (0.01) regalloc - Number of splits that were simple                        
  29 (0.07) slotindexes - Number of local renumberings                          
   1 (0.03) stackslotcoloring - Number of stack slots eliminated due to coloring
   1 (0.00) tailduplication - Additional instructions due to tail duplication   
   1 (0.04) tailduplication - Number of dead blocks removed

Passed all correctness for EEMBC, Spec200X, llvm test-suite. Performance results look to be mostly noise with minor improvements here and there.

Chad

[gberry]

lib/Target/AArch64/AArch64InstrInfo.cpp

1554

Don't you need to check this for Offset2 as well?

Also, I'm not sure what the style guide says, but should this be?

if (Offset1 % OffsetStride != 0)

[mcrosier]

Update per Geoff's comments.

I collected the stats for Spec2006 again and they're verbatim the same. The code make fewer changes to the schedule, however, so it looks like adding the check for offset2 removed a small amount of skewing in the schedule that would never result in a pair being generated.

[mcrosier]

lib/Target/AArch64/AArch64InstrInfo.cpp

1554

Yes, I believe you're correct. We do need to check Offset2 as well.

I'll make the style change as well.

[mcrosier]

Fix an off by 1 error when checking the offset range.
Add a test case.

[mcrosier]

Add support for clustering sext and zext loads and associated test case.

[mcrosier]

Ping.

[gberry]

test/CodeGen/AArch64/arm64-ldp-cluster.ll

3

Perhaps you should add some CHECK statements to verify that the loads you are interested in correspond to the SU nodes you are checking?

[mcrosier]

Update test case, per Geoff's request.

[junbuml]

We do not handle the unscaled + scaled case in this patch, right ?

test/CodeGen/AArch64/arm64-ldp-cluster.ll

21

I think we can also add a test for zext + sext loads as well.

[mcrosier]

In D18048#377268, @junbuml wrote:

We do not handle the unscaled + scaled case in this patch, right ?

Correct.

[mcrosier]

Address Jun's comments. Add a test case for zext + sext clustering. As a bonus I also added a test for ldr (without sext).

[gberry]

lib/Target/AArch64/AArch64InstrInfo.cpp

1502

Do we always merge zext with sext loads? I would think this would be controlled by the subtarget check we do for combining narrow loads since this combination has the same trade off with load vs arith and increased depency chain?

1519

Shouldn't we be checking isCandidateToMergeOrPair here to avoid clustering loads that we're not going to pair?

[mcrosier]

lib/Target/AArch64/AArch64InstrInfo.cpp

1502

Yes; these are unconditionally merged in the load/store optimization pass.

1519

This is the purpose of the canPairLdStOpc() check. It's effectively the pairing logic from the load/store optimizer isCandidateToMergeOrPair() function, but without the merging logic.

[gberry]

lib/Target/AArch64/AArch64InstrInfo.cpp

1502

Okay. It seems like we may want to reconsider this.

1519

But canPairLdStOpc() is only considering the opcode. It doesn't take into account the other things that may inhibit pairing later such as isLdStSuppressed being true. You may be asking the scheduler to cluster loads that you're not going to end up pariing later.

[mcrosier]

lib/Target/AArch64/AArch64InstrInfo.cpp

1519

Ah, I see what you're saying. Let me see if I can move that function into InstrInfo, so it can be shared.

[mcrosier]

Use the isCandidateToMergeOrPair() directly in shouldClusterLoads. This prevents us from clustering loads that can't possibly be paired.

Interestingly, this fix didn't change code generation for SPEC200X. My assumption is the scheduler doesn't really touch volatiles or MI's without MMOs and the load/store suppression only applies to stores (which we don't currently cluster). The remaining check is to make sure the load/store doesn't modify the base register and I'm guessing that rarely/never happens. Regardless, I agree this is the correct thing to do.

[mcrosier]

lib/Target/AArch64/AArch64InstrInfo.cpp

1502

Shall I file a bug or something?

[gberry]

This looks good to me now

lib/Target/AArch64/AArch64InstrInfo.cpp

1502

Sure. I think we should track this along with the narrow load merging issue.

[mcrosier]

Per Geoff's comment.

lib/Target/AArch64/AArch64InstrInfo.cpp

bool AArch64InstrInfo::getMemOpBaseRegImmOfs(
   case AArch64::STRQui:
   case AArch64::STRXui:
   case AArch64::STRWui:
   case AArch64::LDRSui:
   case AArch64::LDRDui:
   case AArch64::LDRQui:
   case AArch64::LDRXui:
   case AArch64::LDRWui:
+  case AArch64::LDRSWui:
+  // Unscaled instructions.
+  case AArch64::LDURSi:
+  case AArch64::LDURDi:
+  case AArch64::LDURQi:
+  case AArch64::LDURWi:
+  case AArch64::LDURXi:
+  case AArch64::LDURSWi:
     unsigned Width;
     return getMemOpBaseRegImmOfsWidth(LdSt, BaseReg, Offset, Width, TRI);
   };
 }
 
 bool AArch64InstrInfo::getMemOpBaseRegImmOfsWidth(
     MachineInstr *LdSt, unsigned &BaseReg, int64_t &Offset, unsigned &Width,
     const TargetRegisterInfo *TRI) const {
case AArch64::STRQui:
     break;
   case AArch64::LDRXui:
   case AArch64::LDRDui:
   case AArch64::STRXui:
   case AArch64::STRDui:
     Scale = Width = 8;
     break;
   case AArch64::LDRWui:
+  case AArch64::LDRSWui:
   case AArch64::LDRSui:
   case AArch64::STRWui:
   case AArch64::STRSui:
     Scale = Width = 4;
     break;
   case AArch64::LDRHui:
   case AArch64::LDRHHui:
   case AArch64::STRHui:
   case AArch64::STRHHui:
     Scale = Width = 2;
     break;
   case AArch64::LDRBui:
   case AArch64::LDRBBui:
   case AArch64::STRBui:
   case AArch64::STRBBui:
     Scale = Width = 1;
     break;
   }
 
   BaseReg = LdSt->getOperand(1).getReg();
   Offset = LdSt->getOperand(2).getImm() * Scale;
   return true;
 }
 
+// Scale the unscaled offsets.  Returns false if the unscaled offset can't be
+// scaled.
+static bool scaleOffset(unsigned Opc, int64_t &Offset) {
+  unsigned OffsetStride = 1;
+  switch (Opc) {
+  default:
+    return false;
+  case AArch64::LDURQi:
+    OffsetStride = 16;
+    break;
+  case AArch64::LDURXi:
+  case AArch64::LDURDi:
+    OffsetStride = 8;
+    break;
+  case AArch64::LDURWi:
+  case AArch64::LDURSi:
+  case AArch64::LDURSWi:
+    OffsetStride = 4;
+    break;
+  }
+  // If the byte-offset isn't a multiple of the stride, we can't scale this
+  // offset.
+  if (Offset % OffsetStride != 0)
+    return false;
+
+  // Convert the byte-offset used by unscaled into an "element" offset used
+  // by the scaled pair load/store instructions.
+  Offset /= OffsetStride;
+  return true;
+}
+
+static bool canPairLdStOpc(unsigned FirstOpc, unsigned SecondOpc) {
+  if (FirstOpc == SecondOpc)
+    return true;
+  // We can also pair sign-ext and zero-ext instructions.
+  switch (FirstOpc) {
+  default:
+    return false;
+  case AArch64::LDRWui:
+  case AArch64::LDURWi:
+    return SecondOpc == AArch64::LDRSWui || SecondOpc == AArch64::LDURSWi;
+  case AArch64::LDRSWui:
+  case AArch64::LDURSWi:
+    return SecondOpc == AArch64::LDRWui || SecondOpc == AArch64::LDURWi;
+  }
+  // These instructions can't be paired based on their opcodes.
+  return false;
+}
+
 /// Detect opportunities for ldp/stp formation.
 ///
 /// Only called for LdSt for which getMemOpBaseRegImmOfs returns true.
 bool AArch64InstrInfo::shouldClusterLoads(MachineInstr *FirstLdSt,
                                           MachineInstr *SecondLdSt,
                                           unsigned NumLoads) const {
   // Only cluster up to a single pair.
   if (NumLoads > 1)
     return false;
-  if (FirstLdSt->getOpcode() != SecondLdSt->getOpcode())
+
+  // Can we pair these instructions based on their opcodes?
+  unsigned FirstOpc = FirstLdSt->getOpcode();
+  unsigned SecondOpc = SecondLdSt->getOpcode();
+  if (!canPairLdStOpc(FirstOpc, SecondOpc))
     return false;
-  // getMemOpBaseRegImmOfs guarantees that oper 2 isImm.
-  unsigned Ofs1 = FirstLdSt->getOperand(2).getImm();
-  // Allow 6 bits of positive range.
-  if (Ofs1 > 64)
+
+  // getMemOpBaseRegImmOfs guarantees that operand 2 isImm.
+  int64_t Offset1 = FirstLdSt->getOperand(2).getImm();
+  if (isUnscaledLdSt(FirstOpc) && !scaleOffset(FirstOpc, Offset1))
     return false;
+
+  int64_t Offset2 = SecondLdSt->getOperand(2).getImm();
+  if (isUnscaledLdSt(SecondOpc) && !scaleOffset(SecondOpc, Offset2))
+    return false;
+
+  // Pairwise instructions have a 7-bit signed offset field.
+  if (Offset1 > 63 || Offset1 < -64)
+    return false;
+
   // The caller should already have ordered First/SecondLdSt by offset.
-  unsigned Ofs2 = SecondLdSt->getOperand(2).getImm();
-  return Ofs1 + 1 == Ofs2;
+  assert(Offset1 <= Offset2 && "Caller should have ordered offsets.");
+  return Offset1 + 1 == Offset2;
 }
 
 bool AArch64InstrInfo::shouldScheduleAdjacent(MachineInstr *First,
                                               MachineInstr *Second) const {
   if (Subtarget.isCyclone()) {
     // Cyclone can fuse CMN, CMP, TST followed by Bcc.
     unsigned SecondOpcode = Second->getOpcode();
     if (SecondOpcode == AArch64::Bcc) {
       switch (First->getOpcode()) {
       default:
         return false;
       case AArch64::SUBSWri:
       case AArch64::ADDSWri:
       case AArch64::ANDSWri:
       case AArch64::SUBSXri:
       case AArch64::ADDSXri:
       case AArch64::ANDSXri:
         return true;

test/CodeGen/AArch64/arm64-ldp-cluster.ll

+; REQUIRES: asserts
+; RUN: llc < %s -mtriple=arm64-linux-gnu -mcpu=cortex-a57 -verify-misched -debug-only=misched -o - 2>&1 > /dev/null | FileCheck %s
+
+; Test ldpsw clustering
+; CHECK: ********** MI Scheduling **********
+; CHECK: ldp_sext_int:BB#0
+; CHECK: Cluster loads SU(1) - SU(2)
+define i64 @ldp_sext_int(i32* %p) nounwind {
+  %tmp = load i32, i32* %p, align 4
+  %add.ptr = getelementptr inbounds i32, i32* %p, i64 1
+  %tmp1 = load i32, i32* %add.ptr, align 4
+  %sexttmp = sext i32 %tmp to i64
+  %sexttmp1 = sext i32 %tmp1 to i64
+  %add = add nsw i64 %sexttmp1, %sexttmp
+  ret i64 %add
+}
+
+; Test sext + zext loads.
+; CHECK: ********** MI Scheduling **********
+; CHECK: ldp_half_sext_int:BB#0
+; CHECK: Cluster loads SU(3) - SU(4)
+define i64 @ldp_half_sext_int(i64* %q, i32* %p) nounwind {
+  %tmp0 = load i64, i64* %q, align 4
+  %tmp = load i32, i32* %p, align 4
+  %add.ptr = getelementptr inbounds i32, i32* %p, i64 1
+  %tmp1 = load i32, i32* %add.ptr, align 4
+  %sexttmp = sext i32 %tmp to i64
+  %sexttmp1 = zext i32 %tmp1 to i64
+  %add = add nsw i64 %sexttmp1, %sexttmp
+  %add1 = add nsw i64 %add, %tmp0
+  ret i64 %add1
+}
+
+; Test ldur clustering.
+define i32 @ldur_int(i32* %a) nounwind {
+; CHECK: ********** MI Scheduling **********
+; CHECK: ldur_int:BB#0
+; CHECK: Cluster loads SU(2) - SU(1)
+  %p1 = getelementptr inbounds i32, i32* %a, i32 -1
+  %tmp1 = load i32, i32* %p1, align 2
+  %p2 = getelementptr inbounds i32, i32* %a, i32 -2
+  %tmp2 = load i32, i32* %p2, align 2
+  %tmp3 = add i32 %tmp1, %tmp2
+  ret i32 %tmp3
+}