Generate better two address code by using commutativity

Generate better two address code by using commutativity

For operations such as
    t0 = t1 + t2
Subzero's pattern for arithmetic operations generates two address code that
looks like
    movl ...t1..., %ecx
    addl ...t2..., %ecx // t0 is in %ecx

When register pressure is high this sometimes becomes:
    movl ...t2..., SPILL
    movl ...t1..., %ecx
    addl SPILL, %ecx // t0 is in %ecx

This CL takes advantage of cases where the use of t2 is the last one, so the
register that held t2 before the operation can be reused.  The optimization
simply swaps the (commutative) operation to
    t0 = t2 + t1
which then generates code as
    movl ...t2..., %ecx
    addl ...t1..., %ecx // t0 is in %ecx

This optimization is used for any commutative operation, which now includes
Fadd and Fmul, which were erroneously marked as non-commutative.  See the
rationale in IceInst.def for the IEEE wordings.

BUG=
R=jfb@chromium.org, stichnot@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=487bad0253e0d70d0cb191e8e5c71d01bf0044ee

[sehr, 2015-09-25 20:40:17]

sehr@chromium.org changed reviewers:
+ jfb@chromium.org, stichnot@chromium.org

[sehr, 2015-09-25 20:40:27]

PTAL.

[JF, 2015-09-25 21:02:50]

lgtm

[Jim Stichnoth, 2015-09-25 21:12:09]

Also can you add a test?

https://codereview.chromium.org/1371703003/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1371703003/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:1289: std::swap(Src0, Src1);
I'm starting to get nervous about "swap wars".  Could you add code to count how
many swaps are performed, and then assert that the count is at most 1?

Perhaps the cleaner alternative is to use "else if" instead of "if", but I like
the counting approach which may catch unexpected behavior in the future.

[sehr, 2015-10-06 18:42:00]

Changed and added a test.  PTAL.

https://codereview.chromium.org/1371703003/diff/1/src/IceTargetLoweringX86Bas...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/1371703003/diff/1/src/IceTargetLoweringX86Bas...
src/IceTargetLoweringX86BaseImpl.h:1289: std::swap(Src0, Src1);
On 2015/09/25 21:12:09, stichnot wrote:
> I'm starting to get nervous about "swap wars".  Could you add code to count
how
> many swaps are performed, and then assert that the count is at most 1?
> 
> Perhaps the cleaner alternative is to use "else if" instead of "if", but I
like
> the counting approach which may catch unexpected behavior in the future.

I added the counter.

[Jim Stichnoth, 2015-10-06 19:35:49]

https://chromiumcodereview.appspot.com/1371703003/diff/40001/tests_lit/llvm2i...
File tests_lit/llvm2ice_tests/commutativity.ll (right):

https://chromiumcodereview.appspot.com/1371703003/diff/40001/tests_lit/llvm2i...
tests_lit/llvm2ice_tests/commutativity.ll:20: ; CHECK-NOT: mov
[[REG1:e.x]],[[REG2:e.x]]
A few problems here.

1. You're matching eax/ebx/ecx/edx but not ebp/esi/edi?

2. The [[pattern]] usage is probably wrong here.  It's used for "capturing"
patterns and checking for exact repetition later.  Maybe you meant {{pattern}}
for non-captured regular expressions? 
http://llvm.org/docs/CommandGuide/FileCheck.html

3. I think the test could be better as something like this:

declare void @dummy()

define i32 @integerAddLeft(i32 %a, i32 %b) {
entry:
  call void @dummy()
  %tmp = add i32 %a, %b
  %result = add i32 %a, %tmp
  ret i32 %result
}
; CHECK-LABEL: integerAddLeft
; CHECK: call dummy
; CHECK-NEXT: add {{e..}},{{e..}}
; CHECK-NEXT: add {{e..}},{{e..}}

The "call dummy" trick lets you know that we're out of the prolog.

A failing test would have a mov between the call and the first add instruction.

[sehr, 2015-10-07 00:18:30]

PTAL.

https://chromiumcodereview.appspot.com/1371703003/diff/40001/tests_lit/llvm2i...
File tests_lit/llvm2ice_tests/commutativity.ll (right):

https://chromiumcodereview.appspot.com/1371703003/diff/40001/tests_lit/llvm2i...
tests_lit/llvm2ice_tests/commutativity.ll:20: ; CHECK-NOT: mov
[[REG1:e.x]],[[REG2:e.x]]
On 2015/10/06 19:35:49, stichnot wrote:
> A few problems here.
> 
> 1. You're matching eax/ebx/ecx/edx but not ebp/esi/edi?
> 
> 2. The [[pattern]] usage is probably wrong here.  It's used for "capturing"
> patterns and checking for exact repetition later.  Maybe you meant {{pattern}}
> for non-captured regular expressions? 
> http://llvm.org/docs/CommandGuide/FileCheck.html
> 
> 3. I think the test could be better as something like this:
> 
> declare void @dummy()
> 
> define i32 @integerAddLeft(i32 %a, i32 %b) {
> entry:
>   call void @dummy()
>   %tmp = add i32 %a, %b
>   %result = add i32 %a, %tmp
>   ret i32 %result
> }
> ; CHECK-LABEL: integerAddLeft
> ; CHECK: call dummy
> ; CHECK-NEXT: add {{e..}},{{e..}}
> ; CHECK-NEXT: add {{e..}},{{e..}}
> 
> The "call dummy" trick lets you know that we're out of the prolog.
> 
> A failing test would have a mov between the call and the first add
instruction.

Completely revamped per your comments here and in hangouts.

[Jim Stichnoth, 2015-10-07 00:29:24]

lgtm

[sehr, 2015-10-07 00:41:30]

Committed patchset #4 (id:60001) manually as
487bad0253e0d70d0cb191e8e5c71d01bf0044ee (presubmit successful).