[TwoAddressInstructionPass] Try 3 Addr Conversion After Commuting

[volkan]

Summary

TwoAddressInstructionPass stops after a successful commuting but 3 Addr conversion might be good for some cases.
Consider:

int foo(int a, int b) {
  return a + b;
}

LLVM emits:

addl	%esi, %edi
movl	%edi, %eax
ret

If we try 3 Addr conversion:

leal	(%rsi,%rdi), %eax
ret

This patch is going to produce one less instruction and save one byte.

[qcolombet]

Hi Volkan,

LGTM.

Thanks,
-Quentin

[qcolombet]

(Actually switch the action drop box!)

llvm/trunk/lib/CodeGen/TwoAddressInstructionPass.cpp

if (regCIdx != ~0U) {
         TryCommute = true;
       else if (isProfitableToCommute(regA, regB, regC, &MI, Dist)) {
         TryCommute = true;
         AggressiveCommute = true;
       }
     }
   }
 
+  // If the instruction is convertible to 3 Addr, instead
+  // of returning try 3 Addr transformation aggresively and
+  // use this variable to check later. Because it might be better.
+  // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret`
+  // instead of the following code.
+  //   addl %esi, %edi
+  //   movl %edi, %eax
+  //   ret
+  bool commuted = false;
+
   // If it's profitable to commute, try to do so.
   if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) {
+    commuted = true;
     ++NumCommuted;
     if (AggressiveCommute)
       ++NumAggrCommuted;
+    if (!MI.isConvertibleTo3Addr())
       return false;
   }
 
   if (shouldOnlyCommute)
     return false;
 
   // If there is one more use of regB later in the same MBB, consider
   // re-schedule this MI below it.
-  if (EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
+  if (!commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) {
     ++NumReSchedDowns;
     return true;
   }
 
   if (MI.isConvertibleTo3Addr()) {
     // This instruction is potentially convertible to a true
     // three-address instruction.  Check if it is profitable.
     if (!regBKilled || isProfitableToConv3Addr(regA, regB)) {
       // Try to convert it.
       if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) {
         ++NumConvertedTo3Addr;
         return true; // Done with this instruction.
       }
     }
   }
 
+  // Return if it is commuted but 3 addr conversion is failed.
+  if (commuted)
+    return false;
+
   // If there is one more use of regB later in the same MBB, consider
   // re-schedule it before this MI if it's legal.
   if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) {
     ++NumReSchedUps;
     return true;
   }
 
   // If this is an instruction with a load folded into it, try unfolding

llvm/trunk/test/CodeGen/X86/commute-two-addr.ll

 
 ; rdar://8762995
 %0 = type { i64, i32 }
 
 define %0 @t3(i32 %lb, i8 zeroext %has_lb, i8 zeroext %lb_inclusive, i32 %ub, i8 zeroext %has_ub, i8 zeroext %ub_inclusive) nounwind {
 entry:
 ; DARWIN-LABEL: t3:
 ; DARWIN: shlq $32, %rcx
-; DARWIN-NEXT: orq %rcx, %rax
+; DARWIN-NEXT: leaq (%rax,%rcx), %rax
 ; DARWIN-NEXT: shll $8
 ; DARWIN-NOT: leaq
   %tmp21 = zext i32 %lb to i64
   %tmp23 = zext i32 %ub to i64
   %tmp24 = shl i64 %tmp23, 32
   %ins26 = or i64 %tmp24, %tmp21
   %tmp28 = zext i8 %has_lb to i32
   %tmp33 = zext i8 %has_ub to i32

llvm/trunk/test/CodeGen/X86/twoaddr-lea.ll

 
 ; rdar://8977508
 ; The second add should not be transformed to leal nor should it be
 ; commutted (which would require inserting a copy).
 define i32 @test2(i32 inreg %a, i32 inreg %b, i32 %c, i32 %d) nounwind {
 entry:
 ; CHECK-LABEL: test2:
 ; CHECK: leal
-; CHECK-NOT: leal
-; CHECK-NOT: mov
+; CHECK-NEXT: addl
 ; CHECK-NEXT: addl
 ; CHECK-NEXT: ret
  %add = add i32 %b, %a
  %add3 = add i32 %add, %c
  %add5 = add i32 %add3, %d
  ret i32 %add5
 }
 

llvm/trunk/test/CodeGen/X86/win64_params.ll

 ; RUN: llc < %s -mtriple=x86_64-pc-win32 | FileCheck %s
 ; RUN: llc < %s -mtriple=x86_64-pc-linux | FileCheck %s -check-prefix=LINUX
 
 ; Verify that the 5th and 6th parameters are coming from the correct location
 ; on the stack.
 define i32 @f6(i32 %p1, i32 %p2, i32 %p3, i32 %p4, i32 %p5, i32 %p6) nounwind readnone optsize {
 entry:
 ; CHECK: movl    48(%rsp), %eax
 ; CHECK: addl    40(%rsp), %eax
-; LINUX: addl    %r9d, %r8d
-; LINUX: movl    %r8d, %eax
+; LINUX: leal    (%r8,%r9), %eax
   %add = add nsw i32 %p6, %p5
   ret i32 %add
 }
 
 define x86_64_win64cc i32 @f7(i32 %p1, i32 %p2, i32 %p3, i32 %p4, i32 %p5, i32 %p6) nounwind readnone optsize {
 entry:
 ; CHECK: movl    48(%rsp), %eax
 ; CHECK: addl    40(%rsp), %eax
 ; LINUX: movl    48(%rsp), %eax
 ; LINUX: addl    40(%rsp), %eax
   %add = add nsw i32 %p6, %p5
   ret i32 %add
 }
 
 ; Verify that even though we're compiling for Windows, parameters behave as
 ; on other platforms here (note the x86_64_sysvcc calling convention).
 define x86_64_sysvcc i32 @f8(i32 %p1, i32 %p2, i32 %p3, i32 %p4, i32 %p5, i32 %p6) nounwind readnone optsize {
 entry:
-; CHECK: addl    %r9d, %r8d
-; CHECK: movl    %r8d, %eax
-; LINUX: addl    %r9d, %r8d
-; LINUX: movl    %r8d, %eax
+; CHECK: leal    (%r8,%r9), %eax
+; LINUX: leal    (%r8,%r9), %eax
   %add = add nsw i32 %p6, %p5
   ret i32 %add
 }

llvm/trunk/test/Transforms/LoopStrengthReduce/X86/ivchain-stress-X86.ll

 ; X64: %for.body.1
 
 ; X32: sharedidx:
 ; X32: %for.body.2
 ; X32: add
 ; X32: add
 ; X32: add
 ; X32: add
-; X32: add
+; X32: leal
 ; X32: %for.body.3
 define void @sharedidx(i8* nocapture %a, i8* nocapture %b, i8* nocapture %c, i32 %s, i32 %len) nounwind ssp {
 entry:
   %cmp8 = icmp eq i32 %len, 0
   br i1 %cmp8, label %for.end, label %for.body
 
 for.body:                                         ; preds = %entry, %for.body.3
   %i.09 = phi i32 [ %add5.3, %for.body.3 ], [ 0, %entry ]