[x86] try harder to form LEA from ADD to avoid flag conflicts (PR40483)

[spatel]

Summary

LEA doesn't affect flags, so use it more liberally to replace an ADD when we know that the ADD operands affect flags.

In the motivating example from PR40483:
https://bugs.llvm.org/show_bug.cgi?id=40483
...this lets us avoid duplicating a math op just to avoid flag conflict.

[grandinj]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

2487 ↗

(On Diff #209731)

Should this not be an || condition ?

[spatel]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

2487 ↗

(On Diff #209731)

It could be || (and I tried that initially), but I saw possible regressions (missed load folding) with that logic.

Given that this is a heuristic, it's hard to determine statically when it will be profitable.

Ok if I add a TODO comment about extending this in a follow-up patch? If we can recover the load folding, I agree that using || would be better.

[grandinj]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

2487 ↗

(On Diff #209731)

Sounds reasonable (noting that I am just a bystander here, not a real reviewer)

[RKSimon]

LGTM - @craig.topper any comments?

[craig.topper]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

2482 ↗

(On Diff #209731)

Should we make sure the flag output has a user? ADC/SBB could definitely only have a live flag input. Not sure about the others.

[spatel]

llvm/lib/Target/X86/X86ISelDAGToDAG.cpp

2482 ↗

(On Diff #209731)

Yes, that seems safer, although we do try to reduce back to regular opcodes if the flag wasn't needed. I don't see any test diffs with a draft of that change.

[spatel]

Patch updated:

1. Check flag uses to avoid unintended transform.
2. Add TODO comment about && vs. ||.

[craig.topper]

Are the multiply test changes due to the flags being used by seto? But seto usage should never be in danger of creating the instruction duplication we're seeing in the motivating case. It does look like we're getting an improvement on those tests, but not for the reason we're selecting LEA.

[spatel]

In D64707#1586664, @craig.topper wrote:

Are the multiply test changes due to the flags being used by seto? But seto usage should never be in danger of creating the instruction duplication we're seeing in the motivating case. It does look like we're getting an improvement on those tests, but not for the reason we're selecting LEA.

Yes, I think you're right - we have something like this:

t95: i32,i32 = X86ISD::ADD t73:1, t93
t102: i32,i32 = X86ISD::UMUL t36, t38
t106: i32,i32 = X86ISD::UMUL t40, t33
  t93: i32 = add t106, t102
        t107: i8 = X86ISD::SETCC Constant:i8<0>, t106:1
      t104: i8 = X86ISD::SETCC Constant:i8<0>, t102:1

So the use of LEA is presumably just making things easier for register allocation.
Not sure how to handle this:

1. Remove UMUL/SMUL from the cases in this patch and forego those improvements.
2. Add a comment expanding on our reasoning for the transform and keep the improvements.
3. Refine the flags check somehow (and again forego those improvements in this patch)?

[RKSimon]

If we focussed just on PR40483 for now - do we just need X86ISD ADD + SUB (ADC + SBB) ?

[spatel]

In D64707#1591179, @RKSimon wrote:

If we focussed just on PR40483 for now - do we just need X86ISD ADD + SUB (ADC + SBB) ?

Yes - mul and logic don't need to be in the list to change the motivating bug. I'll comment those opcodes out, and we can make this patch independent of them.

[spatel]

Patch updated:
Just the add/sub opcodes for now.

[RKSimon]

LGTM - cheers. Ideally we'd get this into the 9.00 release branch.

llvm/trunk/lib/Target/X86/X86ISelDAGToDAG.cpp

bool X86DAGToDAGISel::selectLEAAddr(SDValue N,
   if (AM.hasSymbolicDisplacement()) {
     // For X86-64, always use LEA to materialize RIP-relative addresses.
     if (Subtarget->is64Bit())
       Complexity = 4;
     else
       Complexity += 2;
   }
 
+  // Heuristic: try harder to form an LEA from ADD if the operands set flags.
+  // Unlike ADD, LEA does not affect flags, so we will be less likely to require
+  // duplicating flag-producing instructions later in the pipeline.
+  if (N.getOpcode() == ISD::ADD) {
+    auto isMathWithFlags = [](SDValue V) {
+      switch (V.getOpcode()) {
+      case X86ISD::ADD:
+      case X86ISD::SUB:
+      case X86ISD::ADC:
+      case X86ISD::SBB:
+      /* TODO: These opcodes can be added safely, but we may want to justify
+               their inclusion for different reasons (better for reg-alloc).
+      case X86ISD::SMUL:
+      case X86ISD::UMUL:
+      case X86ISD::OR:
+      case X86ISD::XOR:
+      case X86ISD::AND:
+      */
+        // Value 1 is the flag output of the node - verify it's not dead.
+        return !SDValue(V.getNode(), 1).use_empty();
+      default:
+        return false;
+      }
+    };
+    // TODO: This could be an 'or' rather than 'and' to make the transform more
+    //       likely to happen. We might want to factor in whether there's a
+    //       load folding opportunity for the math op that disappears with LEA.
+    if (isMathWithFlags(N.getOperand(0)) && isMathWithFlags(N.getOperand(1)))
+      Complexity++;
+  }
+
   if (AM.Disp)
     Complexity++;
 
   // If it isn't worth using an LEA, reject it.
   if (Complexity <= 2)
     return false;
 
   getAddressOperands(AM, DL, VT, Base, Scale, Index, Disp, Segment);

llvm/trunk/test/CodeGen/X86/combine-sbb.ll

; X64-NEXT:    retq
   %9 = add i32 %8, %5
   %10 = select i1 %7, i32 %9, i32 0
   ret i32 %10
 }
 
 define i32 @PR40483_sub6(i32*, i32) nounwind {
 ; X86-LABEL: PR40483_sub6:
 ; X86:       # %bb.0:
-; X86-NEXT:    pushl %edi
-; X86-NEXT:    pushl %esi
 ; X86-NEXT:    movl {{[0-9]+}}(%esp), %edx
-; X86-NEXT:    movl (%edx), %esi
-; X86-NEXT:    movl {{[0-9]+}}(%esp), %edi
-; X86-NEXT:    movl %esi, %ecx
-; X86-NEXT:    subl %edi, %ecx
+; X86-NEXT:    movl (%edx), %ecx
 ; X86-NEXT:    xorl %eax, %eax
-; X86-NEXT:    subl %edi, %esi
-; X86-NEXT:    movl %esi, (%edx)
+; X86-NEXT:    subl {{[0-9]+}}(%esp), %ecx
+; X86-NEXT:    movl %ecx, (%edx)
 ; X86-NEXT:    jae .LBB8_2
 ; X86-NEXT:  # %bb.1:
-; X86-NEXT:    addl %ecx, %ecx
-; X86-NEXT:    movl %ecx, %eax
+; X86-NEXT:    leal (%ecx,%ecx), %eax
 ; X86-NEXT:  .LBB8_2:
-; X86-NEXT:    popl %esi
-; X86-NEXT:    popl %edi
 ; X86-NEXT:    retl
 ;
 ; X64-LABEL: PR40483_sub6:
 ; X64:       # %bb.0:
-; X64-NEXT:    movl (%rdi), %ecx
-; X64-NEXT:    movl %ecx, %edx
-; X64-NEXT:    subl %esi, %edx
-; X64-NEXT:    addl %edx, %edx
-; X64-NEXT:    xorl %eax, %eax
-; X64-NEXT:    subl %esi, %ecx
-; X64-NEXT:    movl %ecx, (%rdi)
-; X64-NEXT:    cmovbl %edx, %eax
+; X64-NEXT:    movl (%rdi), %eax
+; X64-NEXT:    xorl %ecx, %ecx
+; X64-NEXT:    subl %esi, %eax
+; X64-NEXT:    movl %eax, (%rdi)
+; X64-NEXT:    leal (%rax,%rax), %eax
+; X64-NEXT:    cmovael %ecx, %eax
 ; X64-NEXT:    retq
   %3 = load i32, i32* %0, align 8
   %4 = tail call { i8, i32 } @llvm.x86.subborrow.32(i8 0, i32 %3, i32 %1)
   %5 = extractvalue { i8, i32 } %4, 1
   store i32 %5, i32* %0, align 8
   %6 = extractvalue { i8, i32 } %4, 0
   %7 = icmp eq i8 %6, 0
   %8 = sub i32 %3, %1
   %9 = add i32 %8, %5
   %10 = select i1 %7, i32 0, i32 %9
   ret i32 %10
 }
 
 declare { i8, i32 } @llvm.x86.subborrow.32(i8, i32, i32)