Subzero. ARM32. New bool folding.

Subzero. ARM32. New bool folding.

Improves the bool folding logic so that branches are short circuited.

BUG= https://code.google.com/p/nativeclient/issues/detail?id=4076
R=stichnot@chromium.org

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

[John, 2015-11-10 16:01:57]

jpp@chromium.org changed reviewers:
+ kschimpf@google.com, sehr@chromium.org, stichnot@chromium.org

[Karl, 2015-11-10 22:25:59]

My main concern is that this (folding) optimization is happening during
lowering, and hence changing the output of -Om1. This makes it hard to test
initial translations.

[John, 2015-11-10 23:05:13]

On 2015/11/10 22:25:59, Karl wrote:
> My main concern is that this (folding) optimization is happening during
> lowering, and hence changing the output of -Om1. This makes it hard to test
> initial translations.

What do you mean, "initial translations?"

tl;dr: the changes improve the geomen in spec2k by 2%, down to 19% worse than
llc -O2.

The changes are minimal for -Om1 are minimal, and fairly understandable.

1) The lowering of
  x = icmp()|fcmp()|trunc()
  br i1 x, l_true, l_false

does not change (or changes slightly.)

2) The lowering of
  x = or(A, B)| and(A, B)
  br i1 x, l_true, l_false

change moderately, to

  cmp A
  jCC l_true (or)| j!CC l_false (and)
  cmp B
  jCC l_true

(btw, gcc -O0 generates this code.)

Previously, this would be:
  and A, 1 --> not always
  and B, 1 --> not always
  cmp A, B
  jCC l_true

which is fine, too.

3) Much of the generated code changed from, e.g.,
  or t, A, B
  and t, t 1 --> but not always
  cmp t, 0
  jeq t_false

to

  tst A, 1
  jne l_true
  tst B, 1
  jne l_true

That's because I changed the lowering from sometimes adding an i?? to i1
truncation to a simple test of the src's LSB.

4) I want to, eventually, go a little further in the expression "tree", and be
able to emit code like

A = evalA()
tst A, 1
jne l_true
b = evalB()
tst B, 1
jne l_true

Then, I believe, these optimizations will shine a bit more. Obviously, delaying
evalB() does not make sense if evalB() is, e.g., an integer arithmetic
instruction, but it might be beneficial if it involves, e.g., memory operations
and/or floating point compare and exchange flags. Note that, for Om1, this
future change will not change the generated code.

Overall, the short circuiting, as implemented right now, might not be optimal,
but we do see a 2% geomean improvement in spec2k, so I would think this is
beneficial.

[Jim Stichnoth, 2015-11-11 00:55:47]

On 2015/11/10 23:05:13, John wrote:
> On 2015/11/10 22:25:59, Karl wrote:
> > My main concern is that this (folding) optimization is happening during
> > lowering, and hence changing the output of -Om1. This makes it hard to test
> > initial translations.
> 
> What do you mean, "initial translations?"
> 
> tl;dr: the changes improve the geomen in spec2k by 2%, down to 19% worse than
> llc -O2.
> 
> The changes are minimal for -Om1 are minimal, and fairly understandable.
> 
> 1) The lowering of
>   x = icmp()|fcmp()|trunc()
>   br i1 x, l_true, l_false
> 
> does not change (or changes slightly.)
> 
> 2) The lowering of
>   x = or(A, B)| and(A, B)
>   br i1 x, l_true, l_false
> 
> change moderately, to
> 
>   cmp A
>   jCC l_true (or)| j!CC l_false (and)
>   cmp B
>   jCC l_true
> 
> (btw, gcc -O0 generates this code.)
> 
> Previously, this would be:
>   and A, 1 --> not always
>   and B, 1 --> not always
>   cmp A, B
>   jCC l_true
> 
> which is fine, too.
> 
> 3) Much of the generated code changed from, e.g.,
>   or t, A, B
>   and t, t 1 --> but not always
>   cmp t, 0
>   jeq t_false
> 
> to
> 
>   tst A, 1
>   jne l_true
>   tst B, 1
>   jne l_true
> 
> That's because I changed the lowering from sometimes adding an i?? to i1
> truncation to a simple test of the src's LSB.
> 
> 4) I want to, eventually, go a little further in the expression "tree", and be
> able to emit code like
> 
> A = evalA()
> tst A, 1
> jne l_true
> b = evalB()
> tst B, 1
> jne l_true
> 
> Then, I believe, these optimizations will shine a bit more. Obviously,
delaying
> evalB() does not make sense if evalB() is, e.g., an integer arithmetic
> instruction, but it might be beneficial if it involves, e.g., memory
operations
> and/or floating point compare and exchange flags. Note that, for Om1, this
> future change will not change the generated code.
> 
> Overall, the short circuiting, as implemented right now, might not be optimal,
> but we do see a 2% geomean improvement in spec2k, so I would think this is
> beneficial.

I haven't yet absorbed this CL, so the following may or may not be relevant.

The philosophy of Om1 translation is to be the absolute simplest possible. 
Generally each instruction is fully translated in isolation, except aspects that
are absolutely necessary such as register allocation and stack frame layout. 
For these exceptions, we dial back to the minimum possible - register allocation
only for infinite-weight variables, and no stack slot coalescing.  Even trivial
things like strength reduction of multiplies by a power of 2 are suppressed in
Om1.

I noticed the changes in Om1 lit tests, which suggested that bool folding might
be applied even for Om1.  I'm not sure whether that's the case for this CL.  I
believe this is what Karl was referring to.  I'd rather not have any sort of
folding, strength reduction, etc. applied in Om1, though I recognize that in
some cases it may be more disruptive to disable something just for Om1.

At some point we'll want to define an O0 recipe and maybe an O1 recipe that
would include the lowest-cost, highest-benefit passes.

[native-client-reviews_googlegroups.com, 2015-11-11 01:46:38]

"I noticed the changes in Om1 lit tests, which suggested that bool folding
might be applied even for Om1"

 It only means that the lowering for those high level instructions changed.
For example,

x = select foo, a, b

changed from

cmp foo, #0
moveq x, a
movne x, b

to

mov x, b
tst a, #1
movne x, a

The other change you're seeing is because

x = and i1 a, b

used to be lowered with the same code that lowered select:

a = and, #1, maybe
b = and, #1, maybe
cmp a, b
moveq x, 0
movne x, 1

which is now lowered to

x = and a, b
x = and x, #1, iff x needs to be truncated.

Or used to be lowered with

a = and, #1, maybe
b = and, #1, maybe
cmp a, b
moveq x, 0
movne x, 1

and now is

x = or a, b
x = and x, #1, iff x needs to be truncated.


And, finally branches. I take back what I said. In Om1, branches will not
be short circuited, and they are always lowered from

br i1 cond, true, false

to

tst cond, #1
jne true


On Tue, Nov 10, 2015 at 4:55 PM, <stichnot@chromium.org> wrote:

> On 2015/11/10 23:05:13, John wrote:
>
>> On 2015/11/10 22:25:59, Karl wrote:
>> > My main concern is that this (folding) optimization is happening during
>> > lowering, and hence changing the output of -Om1. This makes it hard to
>> test
>> > initial translations.
>>
>
> What do you mean, "initial translations?"
>>
>
> tl;dr: the changes improve the geomen in spec2k by 2%, down to 19% worse
>> than
>> llc -O2.
>>
>
> The changes are minimal for -Om1 are minimal, and fairly understandable.
>>
>
> 1) The lowering of
>>    x = icmp()|fcmp()|trunc()
>>    br i1 x, l_true, l_false
>>
>
> does not change (or changes slightly.)
>>
>
> 2) The lowering of
>>    x = or(A, B)| and(A, B)
>>    br i1 x, l_true, l_false
>>
>
> change moderately, to
>>
>
>    cmp A
>>    jCC l_true (or)| j!CC l_false (and)
>>    cmp B
>>    jCC l_true
>>
>
> (btw, gcc -O0 generates this code.)
>>
>
> Previously, this would be:
>>    and A, 1 --> not always
>>    and B, 1 --> not always
>>    cmp A, B
>>    jCC l_true
>>
>
> which is fine, too.
>>
>
> 3) Much of the generated code changed from, e.g.,
>>    or t, A, B
>>    and t, t 1 --> but not always
>>    cmp t, 0
>>    jeq t_false
>>
>
> to
>>
>
>    tst A, 1
>>    jne l_true
>>    tst B, 1
>>    jne l_true
>>
>
> That's because I changed the lowering from sometimes adding an i?? to i1
>> truncation to a simple test of the src's LSB.
>>
>
> 4) I want to, eventually, go a little further in the expression "tree",
>> and be
>> able to emit code like
>>
>
> A = evalA()
>> tst A, 1
>> jne l_true
>> b = evalB()
>> tst B, 1
>> jne l_true
>>
>
> Then, I believe, these optimizations will shine a bit more. Obviously,
>>
> delaying
>
>> evalB() does not make sense if evalB() is, e.g., an integer arithmetic
>> instruction, but it might be beneficial if it involves, e.g., memory
>>
> operations
>
>> and/or floating point compare and exchange flags. Note that, for Om1, this
>> future change will not change the generated code.
>>
>
> Overall, the short circuiting, as implemented right now, might not be
>> optimal,
>> but we do see a 2% geomean improvement in spec2k, so I would think this is
>> beneficial.
>>
>
> I haven't yet absorbed this CL, so the following may or may not be
> relevant.
>
> The philosophy of Om1 translation is to be the absolute simplest possible.
> Generally each instruction is fully translated in isolation, except
> aspects that
> are absolutely necessary such as register allocation and stack frame
> layout.
> For these exceptions, we dial back to the minimum possible - register
> allocation
> only for infinite-weight variables, and no stack slot coalescing.  Even
> trivial
> things like strength reduction of multiplies by a power of 2 are
> suppressed in
> Om1.
>
> I noticed the changes in Om1 lit tests, which suggested that bool folding
> might
> be applied even for Om1.  I'm not sure whether that's the case for this
> CL.  I
> believe this is what Karl was referring to.  I'd rather not have any sort
> of
> folding, strength reduction, etc. applied in Om1, though I recognize that
> in
> some cases it may be more disruptive to disable something just for Om1.
>
> At some point we'll want to define an O0 recipe and maybe an O1 recipe that
> would include the lowest-cost, highest-benefit passes.
>
> https://codereview.chromium.org/1417393003/
>

-- 
You received this message because you are subscribed to the Google Groups
"Native-Client-Reviews" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to native-client-reviews+unsubscribe@googlegroups.com.
To post to this group, send email to native-client-reviews@googlegroups.com.
Visit this group at http://groups.google.com/group/native-client-reviews.
For more options, visit https://groups.google.com/d/optout.

[Jim Stichnoth, 2015-11-11 18:55:05]

Cool!  A bunch of nits, but otherwise lgtm.

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone
File Makefile.standalone (right):

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone#ne...
Makefile.standalone:421: %.spec2k: %
As discussed offline, consider reverting this Makefile change if you conclude
that my previous change fixed the problem correctly.

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone#ne...
Makefile.standalone:429: +make -f $(call where-am-i) TARGETFLAG='$(TARGETFLAG)'
SPEC='$(SPEC)' ALLSPEC='$(ALLSPEC)' $(ALLSPEC:=.spec2k)
80-col

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
File src/IceTargetLoweringARM32.cpp (right):

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1359: // materialize the Sources, and perform the
operation. We create reguar
regular

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1363: Variable *Src0 =
Func->makeVariable(IceType_i1);
Can you do this instead?
  
  Variable *Src0 = makeReg(IceType_i1);

Then you could presumably remove the "Src0 = legalizeToReg(Src0);" below.

Also, consider naming it Src0R.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1382: llvm_unreachable("Unhandled i1 Op");
llvm::report_fatal_error
here and below

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1879: // No producer, no problem: just do emit
codee to perform (Boolean & 1) and
codee?

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:2098: assert(BoolComputations.getProducerOf(Dest)
== nullptr);
Note the deliberate fallthrough in a comment?

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4455: // FlagsWereSet is used to determine wether
Boolean was fold or not. If not,
whether ... folded

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4456: // and explicit
"and" is probably the wrong word here?  Also, reflow the comment.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4481: // This is a special case: we eagerly
assumed Producer could be fold, but
folded ?

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4489: // emitting  the tst instruction.
single space char between "emitting the"

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
File src/IceTargetLoweringARM32.h (right):

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:162: CondARM32::Cond WhenTrue0;
Can these be const?

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:544: /// ShortCircuitConAndLabel wraps the
condition codes that should be used
ShortCircuitCondAndLabel

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:563: /// lowerInt1ForBranch expands the rooted at
Boolean. It returns the condition
"expands the rooted at Boolean" - I can't figure out how to parse this - is
there a missing word?

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:570: // _br is a convenience wrapper that emits br
instructions to Target.
Can you name it something like BrTarget?  Usually "Target" is reserved for a
TargetLowering pointer.

https://codereview.chromium.org/1417393003/diff/100001/tests_lit/llvm2ice_tes...
File tests_lit/llvm2ice_tests/test_i1.ll (right):

https://codereview.chromium.org/1417393003/diff/100001/tests_lit/llvm2ice_tes...
tests_lit/llvm2ice_tests/test_i1.ll:157: ; ARM32: movne
There is trailing whitespace on this line and several others, which irritates
git.

[John, 2015-11-11 22:19:47]

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone
File Makefile.standalone (right):

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone#ne...
Makefile.standalone:421: %.spec2k: %
On 2015/11/11 18:55:04, stichnot wrote:
> As discussed offline, consider reverting this Makefile change if you conclude
> that my previous change fixed the problem correctly.

Done.

https://codereview.chromium.org/1417393003/diff/100001/Makefile.standalone#ne...
Makefile.standalone:429: +make -f $(call where-am-i) TARGETFLAG='$(TARGETFLAG)'
SPEC='$(SPEC)' ALLSPEC='$(ALLSPEC)' $(ALLSPEC:=.spec2k)
On 2015/11/11 18:55:04, stichnot wrote:
> 80-col

N/A

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
File src/IceTargetLoweringARM32.cpp (right):

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1359: // materialize the Sources, and perform the
operation. We create reguar
On 2015/11/11 18:55:04, stichnot wrote:
> regular

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1363: Variable *Src0 =
Func->makeVariable(IceType_i1);
On 2015/11/11 18:55:04, stichnot wrote:
> Can you do this instead?
>   
>   Variable *Src0 = makeReg(IceType_i1);
> 
> Then you could presumably remove the "Src0 = legalizeToReg(Src0);" below.
> 
> Also, consider naming it Src0R.

N/A

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1382: llvm_unreachable("Unhandled i1 Op");
On 2015/11/11 18:55:04, stichnot wrote:
> llvm::report_fatal_error
> here and below

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:1879: // No producer, no problem: just do emit
codee to perform (Boolean & 1) and
On 2015/11/11 18:55:04, stichnot wrote:
> codee?

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:2098: assert(BoolComputations.getProducerOf(Dest)
== nullptr);
On 2015/11/11 18:55:04, stichnot wrote:
> Note the deliberate fallthrough in a comment?

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4455: // FlagsWereSet is used to determine wether
Boolean was fold or not. If not,
On 2015/11/11 18:55:04, stichnot wrote:
> whether ... folded

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4456: // and explicit
On 2015/11/11 18:55:04, stichnot wrote:
> "and" is probably the wrong word here?  Also, reflow the comment.

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4481: // This is a special case: we eagerly
assumed Producer could be fold, but
On 2015/11/11 18:55:04, stichnot wrote:
> folded ?

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.cpp:4489: // emitting  the tst instruction.
On 2015/11/11 18:55:04, stichnot wrote:
> single space char between "emitting the"

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
File src/IceTargetLoweringARM32.h (right):

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:162: CondARM32::Cond WhenTrue0;
On 2015/11/11 18:55:04, stichnot wrote:
> Can these be const?

They can't. For example, in lowerInt1ForSelect we have

Cond = lowerIcmpCond()

which requires these to be non-const.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:544: /// ShortCircuitConAndLabel wraps the
condition codes that should be used
On 2015/11/11 18:55:05, stichnot wrote:
> ShortCircuitCondAndLabel

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:563: /// lowerInt1ForBranch expands the rooted at
Boolean. It returns the condition
On 2015/11/11 18:55:04, stichnot wrote:
> "expands the rooted at Boolean" - I can't figure out how to parse this - is
> there a missing word?

Done.

https://codereview.chromium.org/1417393003/diff/100001/src/IceTargetLoweringA...
src/IceTargetLoweringARM32.h:570: // _br is a convenience wrapper that emits br
instructions to Target.
On 2015/11/11 18:55:05, stichnot wrote:
> Can you name it something like BrTarget?  Usually "Target" is reserved for a
> TargetLowering pointer.

Done.

https://codereview.chromium.org/1417393003/diff/100001/tests_lit/llvm2ice_tes...
File tests_lit/llvm2ice_tests/test_i1.ll (right):

https://codereview.chromium.org/1417393003/diff/100001/tests_lit/llvm2ice_tes...
tests_lit/llvm2ice_tests/test_i1.ll:157: ; ARM32: movne
On 2015/11/11 18:55:05, stichnot wrote:
> There is trailing whitespace on this line and several others, which irritates
> git.

Done.

[John, 2015-11-11 22:27:01]

Committed patchset #9 (id:160001) manually as
7b3d9cbb1c1697e03c616162382d945f35c37347 (presubmit successful).