[X86] Transform slow LEA_B_I_D/LEA_SLOWBASE_I -> LEA_IS_D/LEA_IS iff base == index

[goldstein.w.n]

Summary

The two 3c LEA cases:

lea D(base, index,1)      -> lea D(,index,2)
lea D(r13/rbp, index)     -> lea D(,r13/rbp,2) // D maybe zero

Current take 2 instructions to transform. We can do a bit better by
using LEA w.o a base if base == index and scale == 1.

[pengfei]

scale > 1 also has bad performation on some microarch, see Intel SOM.

[craig.topper]

This comment was removed by craig.topper.

[goldstein.w.n]

In D141980#4060945, @pengfei wrote:

scale > 1 also has bad performation on some microarch, see Intel SOM.

Any idea which micro arch? I don't see any and can't see any reference in SOM.
SOM says:

For LEA instructions with three source operands and some specific situations, instruction latency has
increased to 3 cycles, and must dispatch via port 1:
— LEA that has all three source operands: base, index, and offset.
— LEA that uses base and index registers where the base is EBP, RBP, or R13.
— LEA that uses RIP relative addressing mode.
— LEA that uses 16-bit addressing mode.

But if that is the case below in l902-l910 we have:

// lea offset(%base,%index,scale), %dst =>
// lea offset( ,%index,scale), %dst; add %base,%dst
NewMI = BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(LEAOpcode))
            .add(Dest)
            .addReg(0)
            .add(Scale)
            .add(Index)
            .add(Offset)
            .add(Segment);

Shouldn't that be removed then?

[goldstein.w.n]

In D141980#4060945, @pengfei wrote:

scale > 1 also has bad performation on some microarch, see Intel SOM.

AFAICT none of the Atom targets (slow lea) have TuningSlow3OpsLEA set. I can add a check for
isAtom if you want though. LMK.

[RKSimon]

An LEA with scale > 1 also forces a slower computation on the AGUs for most AMD cpus

[goldstein.w.n]

In D141980#4061628, @RKSimon wrote:

An LEA with scale > 1 also forces a slower computation on the AGUs for most AMD cpus

I see, is there a flag you know of that you think should guard the transform?

Although keep in mind, this is only hooked in for targets that have TuningSlow3OpsLEA which AFAICT only covers:

KNL
ICL
ICX
TGL
CNL
SKX
CLX
CPX
SKL
ADL
HSW
BDW
SNB
IVB

Which are just the intel lineup. The only concerning one is ADL b.c. it has some atom cores and there where concerns atom has slow LEA_IS although looking at ADL-E on uops.info seems LEA_IS_D is same as LEA_B_I_D (2c latency each) so probably still fine to keep this transform (truthfully ADL probably shouldn't have TuningSlow3OpsLEA set as 2uops basically == 1x lea in worst case LEA on the E cores and the P cores have fast LEA).

[craig.topper]

In D141980#4062735, @goldstein.w.n wrote:

In D141980#4061628, @RKSimon wrote:

An LEA with scale > 1 also forces a slower computation on the AGUs for most AMD cpus

I see, is there a flag you know of that you think should guard the transform?

Although keep in mind, this is only hooked in for targets that have TuningSlow3OpsLEA which AFAICT only covers:

KNL
ICL
ICX
TGL
CNL
SKX
CLX
CPX
SKL
ADL
HSW
BDW
SNB
IVB

Which are just the intel lineup. The only concerning one is ADL b.c. it has some atom cores and there where concerns atom has slow LEA_IS although looking at ADL-E on uops.info seems LEA_IS_D is same as LEA_B_I_D (2c latency each) so probably still fine to keep this transform (truthfully ADL probably shouldn't have TuningSlow3OpsLEA set as 2uops basically == 1x lea in worst case LEA on the E cores and the P cores have fast LEA).

I find it odd that KNL is in that list. KNL is based on Silvermont so I'd expect it to have TuningSlowLEA instead.

[goldstein.w.n]

In D141980#4062758, @craig.topper wrote:

In D141980#4062735, @goldstein.w.n wrote:

In D141980#4061628, @RKSimon wrote:

An LEA with scale > 1 also forces a slower computation on the AGUs for most AMD cpus

I see, is there a flag you know of that you think should guard the transform?

Although keep in mind, this is only hooked in for targets that have TuningSlow3OpsLEA which AFAICT only covers:

KNL
ICL
ICX
TGL
CNL
SKX
CLX
CPX
SKL
ADL
HSW
BDW
SNB
IVB

Which are just the intel lineup. The only concerning one is ADL b.c. it has some atom cores and there where concerns atom has slow LEA_IS although looking at ADL-E on uops.info seems LEA_IS_D is same as LEA_B_I_D (2c latency each) so probably still fine to keep this transform (truthfully ADL probably shouldn't have TuningSlow3OpsLEA set as 2uops basically == 1x lea in worst case LEA on the E cores and the P cores have fast LEA).

I find it odd that KNL is in that list. KNL is based on Silvermont so I'd expect it to have TuningSlowLEA instead.

We have:

X86.td:L1104:
...
  list<SubtargetFeature> KNLTuning = [TuningSlowDivide64,
                                      TuningSlow3OpsLEA,
                                      TuningSlowIncDec,
                                      TuningSlowTwoMemOps,
                                      TuningPreferMaskRegisters,
                                      TuningFastGather,
                                      TuningFastMOVBE,
                                      TuningSlowPMADDWD];

Should it be changed to TuningSlowLEA?

[pengfei]

I think it is just a general improvement to targets have TuningSlow3OpsLEA, despite some arch has limitation the scaled index should not be on the critical path.

I find it odd that KNL is in that list. KNL is based on Silvermont so I'd expect it to have TuningSlowLEA instead.

SOM says some instructions in the Knights Landing microarchitecture ... will have an allocation throughput of one per cycle. Examples of these instructions are: ... LEA with 3 sources So I think it is correct to classify to TuningSlow3OpsLEA.

llvm/lib/Target/X86/X86FixupLEAs.cpp

796

Out of 80 columns.

llvm/test/CodeGen/X86/leaFixup32.mir

381

Should we change the function name to reflect the change? The same for others.

[goldstein.w.n]

Rename tests. Fix fmt

[goldstein.w.n]

Update test that was previously missed

[goldstein.w.n]

Missed a test last time (was only running on x86 codegen). Changes still seem fine, but will wait till after weekend to push if anyone has concerns.

llvm/lib/Target/X86/X86FixupLEAs.cpp

void FixupLEAPass::processInstrForSlow3OpLEA(MachineBasicBlock::iterator &I,
   // to replace the LEA instruction.
   if (IsInefficientBase && DestReg == BaseReg && !IsScale1)
     return;
 
   LLVM_DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MI.dump(););
   LLVM_DEBUG(dbgs() << "FixLEA: Replaced by: ";);
 
   MachineInstr *NewMI = nullptr;
+  bool BaseOrIndexIsDst = DestReg == BaseReg || DestReg == IndexReg;
+  // First try and remove the base while sticking with LEA iff base == index and
+  // scale == 1. We can handle:
+  //    1. lea D(%base,%index,1)   -> lea D(,%index,2)
+  //    2. lea D(%r13/%rbp,%index) -> lea D(,%index,2)
+  // Only do this if the LEA would otherwise be split into 2-instruction
+  // (either it has a an Offset or neither base nor index are dst)
+  if (IsScale1 && BaseReg == IndexReg &&
+      (hasLEAOffset(Offset) || (IsInefficientBase && !BaseOrIndexIsDst))) {
+    NewMI = BuildMI(MBB, MI, MI.getDebugLoc(), TII->get(LEAOpcode))
+                .add(Dest)
+                .addReg(0)
+                .addImm(2)
+                .add(Index)
+                .add(Offset)
+                .add(Segment);
+    LLVM_DEBUG(NewMI->dump(););
 
-  // First try to replace LEA with one or two (for the 3-op LEA case)
+    MBB.getParent()->substituteDebugValuesForInst(*I, *NewMI, 1);
+    MBB.erase(I);
+    I = NewMI;
+    return;
+  } else if (IsScale1 && BaseOrIndexIsDst) {
+    // Try to replace LEA with one or two (for the 3-op LEA case)
     // add instructions:
     // 1.lea (%base,%index,1), %base => add %index,%base
     // 2.lea (%base,%index,1), %index => add %base,%index
-  if (IsScale1 && (DestReg == BaseReg || DestReg == IndexReg)) {
+
     unsigned NewOpc = getADDrrFromLEA(MI.getOpcode());
     if (DestReg != BaseReg)
       std::swap(BaseReg, IndexReg);
 
     if (MI.getOpcode() == X86::LEA64_32r) {
       // TODO: Do we need the super register implicit use?
       NewMI = BuildMI(MBB, I, MI.getDebugLoc(), TII->get(NewOpc), DestReg)
                   .addReg(BaseReg)

llvm/test/CodeGen/X86/leaFixup32.mir

--- |
   }
 
   ;test2addi32_32: 3 operands LEA32r that can be replaced with 2 add instructions where ADD32ri32
   ; is chosen
   define i32 @test2addi32_32() {
     ret i32 0
   }
 
-  ;test1mov1add_ebp_32: 2 operands LEA32r that can be replaced with 1 add 1 mov instructions
+  ;test_leab_ebp_leais_32: 2 operands LEA32r that can be replaced with LEA_IS form
   ; where the base is rbp/r13/ebp register
-  define i32 @test1mov1add_ebp_32() {
+  define i32 @test_leab_ebp_leais_32() {
     ret i32 0
   }
 
-  ;testleaadd_ebp_index_32: 3 operands LEA32r that can be replaced with 1 lea 1 add instructions
+  ;test_leabi_ebp_leais_32: 3 operands LEA32r that can be replaced with LEA_IS form
   ; where the base and the index are ebp register and there is offset
-  define i32 @testleaadd_ebp_index_32() {
+  define i32 @test_leabi_ebp_leais_32() {
     ret i32 0
   }
 
   ;testleaadd_ebp_index2_32: 3 operands LEA32r that can be replaced with 1 lea 1 add instructions
   ; where the base and the index are ebp register and there is scale
   define i32 @testleaadd_ebp_index2_32() {
     ret i32 0
   }
bb.0 (%ir-block.0):
     ; CHECK: $eax = ADD32rr $eax, $ebp, implicit-def $eflags
     ; CHECK: $eax = ADD32ri $eax, 129, implicit-def $eflags
     ; CHECK: RET64 $eax
     $eax = LEA32r killed $eax, 1, killed $ebp, 129, $noreg
     RET64 $eax
 
 ...
 ---
-name:            test1mov1add_ebp_32
+name:            test_leab_ebp_leais_32
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$eax' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $eax, $ebp, $ebx
 
-    ; CHECK-LABEL: name: test1mov1add_ebp_32
+    ; CHECK-LABEL: name: test_leab_ebp_leais_32
     ; CHECK: liveins: $eax, $ebp, $ebx
-    ; CHECK: $ebx = MOV32rr $ebp
-    ; CHECK: $ebx = ADD32rr $ebx, $ebp, implicit-def $eflags
+    ; CHECK: $ebx = LEA32r $noreg, 2, $ebp, 0, $noreg
     ; CHECK: RET64 $ebx
     $ebx = LEA32r killed $ebp, 1, $ebp, 0, $noreg
     RET64 $ebx
 
 ...
 ---
-name:            testleaadd_ebp_index_32
+name:            test_leabi_ebp_leais_32
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$ebx' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $eax, $ebp, $ebx
 
-    ; CHECK-LABEL: name: testleaadd_ebp_index_32
+    ; CHECK-LABEL: name: test_leabi_ebp_leais_32
     ; CHECK: liveins: $eax, $ebp, $ebx
-    ; CHECK: $ebx = LEA32r $noreg, 1, $ebp, 5, $noreg
-    ; CHECK: $ebx = ADD32rr $ebx, $ebp, implicit-def $eflags
+    ; CHECK: $ebx = LEA32r $noreg, 2, $ebp, 5, $noreg
     ; CHECK: RET64 $ebx
     $ebx = LEA32r $ebp, 1, $ebp, 5, $noreg
     RET64 $ebx
 
 ...
 ---
 name:            testleaadd_ebp_index2_32
 alignment:       16

llvm/test/CodeGen/X86/leaFixup64.mir

--- |
   }
 
   ;testleaaddi32_64_32: 3 operands LEA64_32r that can be replaced with 1 lea + 1 add instructions where
   ; ADD64ri32 is chosen
   define i32 @testleaaddi32_64_32() {
     ret i32 0
   }
 
-  ;test1mov1add_rbp_64_32: 2 operands LEA64_32r cannot be replaced with 1 add 1 mov instructions
+  ;test_leab_rbp_leais_64_32: 2 operands LEA64_32r that can be replaced with LEA_IS form
   ; where the base is rbp/r13/ebp register
-  define i32 @test1mov1add_rbp_64_32() {
+  define i32 @test_leab_rbp_leais_64_32() {
     ret i32 0
   }
 
-  ;testleaadd_rbp_index_64_32: 3 operands LEA64_32r that cannot replaced with 1 lea 1 add instructions
+  ;test_leabi_rbp_leais_64_32: 3 operands LEA64_32r that can be replaced with LEA_IS form
   ; where the base and the index are ebp register and there is offset
-  define i32 @testleaadd_rbp_index_64_32() {
+  define i32 @test_leabi_rbp_leais_64_32() {
     ret i32 0
   }
 
   ;testleaadd_rbp_index2_64_32: 3 operands LEA64_32r that cannot replaced with 1 lea 1 add instructions
   ; where the base and the index are ebp register and there is scale
   define i32 @testleaadd_rbp_index2_64_32() {
     ret i32 0
   }
 
   ;test2addi32_64: 3 operands LEA64r that can be replaced with 2 add instructions where ADD64ri32
   ; is chosen
   define i32 @test2addi32_64() {
     ret i32 0
   }
 
-  ;test1mov1add_rbp_64: 2 operands LEA64r that can be replaced with 1 add 1 mov instructions
+  ;test_leab_rbp_leais_64: 2 operands LEA64r that can be replaced with LEA_IS form
   ; where the base is rbp/r13/ebp register
-  define i32 @test1mov1add_rbp_64() {
+  define i32 @test_leab_rbp_leais_64() {
     ret i32 0
   }
 
-  ;testleaadd_rbp_index_64: 3 operands LEA64r that can be replaced with 1 lea 1 add instructions
+  ;test_leabi_rbp_leais_64: 3 operands LEA64r that can be replaced with LEA_IS form
   ; where the base and the index are ebp register and there is offset
-  define i32 @testleaadd_rbp_index_64() {
+  define i32 @test_leabi_rbp_leais_64() {
     ret i32 0
   }
 
   ;testleaadd_rbp_index2_64: 3 operands LEA64r that can be replaced with 1 lea 1 add instructions
   ; where the base and the index are ebp register and there is scale
   define i32 @testleaadd_rbp_index2_64() {
     ret i32 0
   }
bb.0 (%ir-block.0):
     ; CHECK: $eax = ADD32rr $eax, $ebp, implicit-def $eflags, implicit $rax, implicit $rbp
     ; CHECK: $eax = ADD32ri $eax, 129, implicit-def $eflags
     ; CHECK: RET64 $eax
     $eax = LEA64_32r killed $rax, 1, killed $rbp, 129, $noreg
     RET64 $eax
 
 ...
 ---
-name:            test1mov1add_rbp_64_32
+name:            test_leab_rbp_leais_64_32
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$rax' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $rax, $rbp, $rbx
 
-    ; CHECK-LABEL: name: test1mov1add_rbp_64_32
+    ; CHECK-LABEL: name: test_leab_rbp_leais_64_32
     ; CHECK: liveins: $rax, $rbp, $rbx
-    ; CHECK: $ebx = LEA64_32r killed $rbp, 1, killed $rbp, 0, $noreg
+    ; CHECK: $ebx = LEA64_32r $noreg, 2, killed $rbp, 0, $noreg
     ; CHECK: RET64 $ebx
     $ebx = LEA64_32r killed $rbp, 1, killed $rbp, 0, $noreg
     RET64 $ebx
 
 ...
 ---
-name:            testleaadd_rbp_index_64_32
+name:            test_leabi_rbp_leais_64_32
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$rbx' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $rax, $rbp, $rbx
 
-    ; CHECK-LABEL: name: testleaadd_rbp_index_64_32
+    ; CHECK-LABEL: name: test_leabi_rbp_leais_64_32
     ; CHECK: liveins: $rax, $rbp, $rbx
-    ; CHECK: $ebx = LEA64_32r killed $rbp, 1, killed $rbp, 5, $noreg
+    ; CHECK: $ebx = LEA64_32r $noreg, 2, killed $rbp, 5, $noreg
     ; CHECK: RET64 $ebx
     $ebx = LEA64_32r killed $rbp, 1, killed $rbp, 5, $noreg
     RET64 $ebx
 
 ...
 ---
 name:            testleaadd_rbp_index2_64_32
 alignment:       16
bb.0 (%ir-block.0):
     ; CHECK: $rax = ADD64rr $rax, $rbp, implicit-def $eflags
     ; CHECK: $rax = ADD64ri32 $rax, 129, implicit-def $eflags
     ; CHECK: RET64 $eax
     $rax = LEA64r killed $rax, 1, killed $rbp, 129, $noreg
     RET64 $eax
 
 ...
 ---
-name:            test1mov1add_rbp_64
+name:            test_leab_rbp_leais_64
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$rax' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $rax, $rbp, $rbx
 
-    ; CHECK-LABEL: name: test1mov1add_rbp_64
+    ; CHECK-LABEL: name: test_leab_rbp_leais_64
     ; CHECK: liveins: $rax, $rbp, $rbx
-    ; CHECK: $rbx = MOV64rr $rbp
-    ; CHECK: $rbx = ADD64rr $rbx, $rbp, implicit-def $eflags
+    ; CHECK: $rbx = LEA64r $noreg, 2, $rbp, 0, $noreg
     ; CHECK: RET64 $ebx
     $rbx = LEA64r killed $rbp, 1, $rbp, 0, $noreg
     RET64 $ebx
 
 ...
 ---
-name:            testleaadd_rbp_index_64
+name:            test_leabi_rbp_leais_64
 alignment:       16
 exposesReturnsTwice: false
 legalized:       false
 regBankSelected: false
 selected:        false
 tracksRegLiveness: true
 liveins:
   - { reg: '$rbx' }
frameInfo:
   maxCallFrameSize: 0
   hasOpaqueSPAdjustment: false
   hasVAStart:      false
   hasMustTailInVarArgFunc: false
 body:             |
   bb.0 (%ir-block.0):
     liveins: $rax, $rbp, $rbx
 
-    ; CHECK-LABEL: name: testleaadd_rbp_index_64
+    ; CHECK-LABEL: name: test_leabi_rbp_leais_64
     ; CHECK: liveins: $rax, $rbp, $rbx
-    ; CHECK: $rbx = LEA64r $noreg, 1, $rbp, 5, $noreg
-    ; CHECK: $rbx = ADD64rr $rbx, $rbp, implicit-def $eflags
+    ; CHECK: $rbx = LEA64r $noreg, 2, $rbp, 5, $noreg
     ; CHECK: RET64 $ebx
     $rbx = LEA64r $rbp, 1, $rbp, 5, $noreg
     RET64 $ebx
 
 ...
 ---
 name:            testleaadd_rbp_index2_64
 alignment:       16

llvm/test/CodeGen/X86/select-1-or-neg1.ll

 ; BASE-NEXT:    leal -1(%rax,%rax), %eax
 ; BASE-NEXT:    retq
 ;
 ; SLOWLEA3-LABEL: PR28968:
 ; SLOWLEA3:       # %bb.0:
 ; SLOWLEA3-NEXT:    xorl %eax, %eax
 ; SLOWLEA3-NEXT:    cmpl $1, %edi
 ; SLOWLEA3-NEXT:    sete %al
-; SLOWLEA3-NEXT:    addl %eax, %eax
-; SLOWLEA3-NEXT:    decl %eax
+; SLOWLEA3-NEXT:    leal -1(,%rax,2), %eax
 ; SLOWLEA3-NEXT:    retq
   %cmp = icmp eq i32 %x, 1
   %sel = select i1 %cmp, i32 1, i32 -1
   ret i32 %sel
 }
 

llvm/test/DebugInfo/MIR/InstrRef/x86-lea-fixup-2.mir

bb.0:
     liveins: $eax, $ebp
 
     ; CHECK: $eax = ADD32ri8 {{.*}} debug-instr-number 2
     $eax = LEA32r killed $eax, 1, killed $ebp, -5, $noreg, debug-instr-number 1
     RET64 $eax
 
 ...
 ---
-name:            test1mov1add_ebp_32
-# CHECK-LABEL: name: test1mov1add_ebp_32
+name:            testleais_ebp_32
+# CHECK-LABEL: name: testleais_ebp_32
 alignment:       16
 tracksRegLiveness: true
 debugInstrRef: true
 liveins:
   - { reg: '$eax' }
   - { reg: '$ebx' }
   - { reg: '$ebp' }
 # CHECK:       debugValueSubstitutions:
 # CHECK-NEXT:  - { srcinst: 1, srcop: 0, dstinst: 2, dstop: 0, subreg: 0 }
 body:             |
   bb.0:
     liveins: $eax, $ebp, $ebx
 
-    ; CHECK: $ebx = ADD32rr {{.*}} debug-instr-number 2
+    ; CHECK: $ebx = LEA32r $noreg, 2, $ebp, 0, $noreg, debug-instr-number 2
     $ebx = LEA32r killed $ebp, 1, $ebp, 0, $noreg, debug-instr-number 1
     RET64 $ebx
 
 ...
 ---
-name:            testleaadd_ebp_index_32
-# CHECK-LABEL: name: testleaadd_ebp_index_32
+name:            testleabid_ebp_leaisd_32
+# CHECK-LABEL: name: testleabid_ebp_leaisd_32
 alignment:       16
 tracksRegLiveness: true
 debugInstrRef: true
 liveins:
   - { reg: '$ebx' }
   - { reg: '$ebp' }
 # CHECK:       debugValueSubstitutions:
 # CHECK-NEXT:  - { srcinst: 1, srcop: 0, dstinst: 2, dstop: 0, subreg: 0 }
 body:             |
   bb.0:
     liveins: $eax, $ebp, $ebx
 
-    ; CHECK: $ebx = ADD32rr {{.*}} debug-instr-number 2
+    ; CHECK: $ebx = LEA32r $noreg, 2, $ebp, 5, $noreg, debug-instr-number 2
     $ebx = LEA32r $ebp, 1, $ebp, 5, $noreg, debug-instr-number 1
     RET64 $ebx
 
 ...