[arm64] Generate adds/ands.

[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=

Committed: https://crrev.com/317dc0578f21a7dd08568cbd802f6bf82b578591
Cr-Commit-Position: refs/heads/master@{#37400}

[georgia.kouveli, 2016-06-15 15:41:31]

Description was changed from

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=
==========

to

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=
==========

[georgia.kouveli, 2016-06-15 15:41:31]

georgia.kouveli@arm.com changed reviewers:
+ bmeurer@chromium.org, epertoso@chromium.org

[Benedikt Meurer, 2016-06-16 03:39:32]

Thanks for the patch. It seems to be a bit complex on first sight, though. Maybe
we can find a more general approach that also applies naturally to other
platforms with a flags register (i.e. x64/ia32 would certainly also benefit from
this).

The additional flags seem to be redundant. It looks like positive or zero is ge
and negative is lt (same on Intel), or am I missing something? If so we could
probably use SignedLessThan and SignedGreaterThanOrEqual flags.

Also I think the op+branch combination should be possible to express via the
kFlags_branch mechanism, i.e. we already use that for Int32AddWithOverflow.

So the InstructionSelector could do the following I guess:

- In VisitBranch, check if the condition somehow includes a comparison with 0
and one of the fusable ops (i.e. Add, And, Sub, etc.).
- Check if the op is in the same basic block as the comparison (and the branch).
- If so, check that all other users of that op are already scheduled (that means
there's no other user of op in the basic block you are looking at), we do that
for the Projection merging in case of Int32AddWithOverflow already.
- If so, then generate the code for the op with kFlags_branch on it.

[georgia.kouveli, 2016-06-16 12:51:27]

Hi Benedikt,

On 2016/06/16 03:39:32, Benedikt Meurer wrote:
> Thanks for the patch. It seems to be a bit complex on first sight, though.
Maybe
> we can find a more general approach that also applies naturally to other
> platforms with a flags register (i.e. x64/ia32 would certainly also benefit
from
> this).

Regarding a more general approach, I don't understand the details of the other
architectures well enough to know when this would be beneficial, but since the
supported conditions depend on how each individual instruction sets flags (even
for arm and arm64 this is not identical), I think it might be difficult. I'm
also not sure how we could express in a generic way the fact that we want to
generate a "cmn" or a "tst" instruction instead of "adds" or "ands" when the
result (other than the flag) is not used.

> 
> The additional flags seem to be redundant. It looks like positive or zero is
ge
> and negative is lt (same on Intel), or am I missing something? If so we could
> probably use SignedLessThan and SignedGreaterThanOrEqual flags.
> 


The additional conditions are not redundant. PositiveOrZero/Negative check only
the sign bit of the result (the N condition flag, for ARM), whereas
SignedLessThan and SignedGreaterThanOrEqual are affected by overflow, which
depends on the operation performed (for ARM, this means they depend on the V
flag).
For the result of a cmp/sub instruction, these are very similar conditions (but
still not identical), whereas for the result of an add they are completely
different conditions.
An example:
  add w0, w1, w2
  cmp w0, #0x0
  b.lt <target>
maps to
  adds w0, w1, w2
  b.mi <target>
(Not a b.lt). Since we can't support the transformation for all conditions, I
check which ones we can in CanUseFlagSettingBinop and map the condition
accordinly in MapForFlagSettingBinop.


> Also I think the op+branch combination should be possible to express via the
> kFlags_branch mechanism, i.e. we already use that for Int32AddWithOverflow.


This is what the patch does, passing the FlagsContinuation from the branch to
VisitBinop. It's slightly more generic, actually (see below).


> 
> So the InstructionSelector could do the following I guess:
> 
> - In VisitBranch, check if the condition somehow includes a comparison with 0
> and one of the fusable ops (i.e. Add, And, Sub, etc.).
> - Check if the op is in the same basic block as the comparison (and the
branch).
> - If so, check that all other users of that op are already scheduled (that
means
> there's no other user of op in the basic block you are looking at), we do that
> for the Projection merging in case of Int32AddWithOverflow already.
> - If so, then generate the code for the op with kFlags_branch on it.

This sounds very similar to what my code does at the moment:

- The function I am modifying, VisitWord32Compare, gets called from VisitBranch
(via VisitWordCompareZero). This is slightly more generic - we can actually
match an add and a comparison to a flag setting add even if the comparison
is not matched with the branch (VisitWord32Compare is called when visiting
various comparison nodes that might be independent of a branch or we might have
failed to select together with a branch).

- The IsOnlyUserOfNodeInSameBlock check does roughly what you describe,
checking the comparison and add are in the same block and that there are no
other uses of op in the same basic block. Perhaps the IsDefined function that's
used to check that the Projection of the Int32AddWithOverflow has been selected
could be somehow useful, but it's not obvious to me. Simply replacing the
"selector->GetBasicBlock(from) == bb_user" that I do for all users of the add
with "!selector->IsDefined(from)" seems to break my tests (where I use the add
in a return, which is not "defined" and hence the check fails, I suspect
something similar will happen with phi nodes).

- The code for the op will be generated with a kFlags_branch on it when coming
from VisitBranch (which is the case I spotted in benchmarks and in the
interpreter Jump opcodes). But it can also be kFlags_set when coming from
VisitInt32LessThan, for example.

[Benedikt Meurer, 2016-06-16 17:59:57]

Hey Georgia,

Thanks for the explanations. Comments inline.

> > Thanks for the patch. It seems to be a bit complex on first sight, though.
> Maybe
> > we can find a more general approach that also applies naturally to other
> > platforms with a flags register (i.e. x64/ia32 would certainly also benefit
> from
> > this).
> 
> Regarding a more general approach, I don't understand the details of the other
> architectures well enough to know when this would be beneficial, but since the
> supported conditions depend on how each individual instruction sets flags
(even
> for arm and arm64 this is not identical), I think it might be difficult. I'm
> also not sure how we could express in a generic way the fact that we want to
> generate a "cmn" or a "tst" instruction instead of "adds" or "ands" when the
> result (other than the flag) is not used.

Good point.

> > The additional flags seem to be redundant. It looks like positive or zero is
> ge
> > and negative is lt (same on Intel), or am I missing something? If so we
could
> > probably use SignedLessThan and SignedGreaterThanOrEqual flags. 
> 
> The additional conditions are not redundant. PositiveOrZero/Negative check
only
> the sign bit of the result (the N condition flag, for ARM), whereas
> SignedLessThan and SignedGreaterThanOrEqual are affected by overflow, which
> depends on the operation performed (for ARM, this means they depend on the V
> flag).
> For the result of a cmp/sub instruction, these are very similar conditions
(but
> still not identical), whereas for the result of an add they are completely
> different conditions.
> An example:
>   add w0, w1, w2
>   cmp w0, #0x0
>   b.lt <target>
> maps to
>   adds w0, w1, w2
>   b.mi <target>
> (Not a b.lt). Since we can't support the transformation for all conditions, I
> check which ones we can in CanUseFlagSettingBinop and map the condition
> accordinly in MapForFlagSettingBinop.

Also good point. I forgot about that.

> > So the InstructionSelector could do the following I guess:
> > 
> > - In VisitBranch, check if the condition somehow includes a comparison with
0
> > and one of the fusable ops (i.e. Add, And, Sub, etc.).
> > - Check if the op is in the same basic block as the comparison (and the
> branch).
> > - If so, check that all other users of that op are already scheduled (that
> means
> > there's no other user of op in the basic block you are looking at), we do
that
> > for the Projection merging in case of Int32AddWithOverflow already.
> > - If so, then generate the code for the op with kFlags_branch on it.
> 
> This sounds very similar to what my code does at the moment:
> 
> - The function I am modifying, VisitWord32Compare, gets called from
VisitBranch
> (via VisitWordCompareZero). This is slightly more generic - we can actually
> match an add and a comparison to a flag setting add even if the comparison
> is not matched with the branch (VisitWord32Compare is called when visiting
> various comparison nodes that might be independent of a branch or we might
have
> failed to select together with a branch).
> 
> - The IsOnlyUserOfNodeInSameBlock check does roughly what you describe,
> checking the comparison and add are in the same block and that there are no
> other uses of op in the same basic block. Perhaps the IsDefined function
that's
> used to check that the Projection of the Int32AddWithOverflow has been
selected
> could be somehow useful, but it's not obvious to me. Simply replacing the
> "selector->GetBasicBlock(from) == bb_user" that I do for all users of the add
> with "!selector->IsDefined(from)" seems to break my tests (where I use the add
> in a return, which is not "defined" and hence the check fails, I suspect
> something similar will happen with phi nodes).

Ok, so this is the part that I'm not sure about. The thing I don't like about
this is that we expose the BasicBlock access to the backends; I'm not sure why
IsDefined wouldn't do the trick here, but I guess I'd be fine if you could
express the functionality you need in terms of some predicate on the
InstructionSelector that is then exposed to the backends; in a way that we can
implement the functionality of this CL for Intel architectures as well - and
kindly ask you to contribute an arm port :-)
 
> - The code for the op will be generated with a kFlags_branch on it when coming
> from VisitBranch (which is the case I spotted in benchmarks and in the
> interpreter Jump opcodes). But it can also be kFlags_set when coming from
> VisitInt32LessThan, for example.

Ok, sounds reasonable.

[georgia.kouveli, 2016-06-28 15:56:30]

PTAL.

Updated according to your comments. Also rebased to include my VisitBinop fix.
Also made some fixes, the most important:
- kPositiveOrZero and kNegative should not be commuted with
CommuteFlagsCondition.
- The immediate mode was incorrect for ANDS/TST (added test for this).

[Benedikt Meurer, 2016-06-29 03:54:35]

LGTM with nits (and modulo missing bits to make the other ports compile). Do you
plan to port this to ARM as well?

https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
File src/compiler/arm64/instruction-selector-arm64.cc (right):

https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
src/compiler/arm64/instruction-selector-arm64.cc:1932: static bool
CanUseFlagSettingBinop(FlagsCondition cond) {
Nit: You don't need static inside an anonymous namespace.

https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
src/compiler/arm64/instruction-selector-arm64.cc:1951: static FlagsCondition
MapForFlagSettingBinop(FlagsCondition cond) {
Nit: You don't need static inside an anonymous namespace.

[georgia.kouveli, 2016-06-29 10:00:14]

Yes, I plan to port this to ARM.

About the other ports: they are using "default" statements when handling
FlagsCondition (and my new flags are not the only ones not handled explicitly).
"make release" and "make debug" are OK, I tried some of the other ports too (no
new build errors with my patch). Am I missing something?

On 2016/06/29 03:54:35, Benedikt Meurer wrote:
> LGTM with nits (and modulo missing bits to make the other ports compile). Do
you
> plan to port this to ARM as well?
> 
>
https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
> File src/compiler/arm64/instruction-selector-arm64.cc (right):
> 
>
https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
> src/compiler/arm64/instruction-selector-arm64.cc:1932: static bool
> CanUseFlagSettingBinop(FlagsCondition cond) {
> Nit: You don't need static inside an anonymous namespace.
> 
>
https://codereview.chromium.org/2065243005/diff/60001/src/compiler/arm64/inst...
> src/compiler/arm64/instruction-selector-arm64.cc:1951: static FlagsCondition
> MapForFlagSettingBinop(FlagsCondition cond) {
> Nit: You don't need static inside an anonymous namespace.

[georgia.kouveli, 2016-06-29 14:29:16]

The CQ bit was checked by georgia.kouveli@arm.com

[georgia.kouveli, 2016-06-29 14:29:16]

The patchset sent to the CQ was uploaded after l-g-t-m from bmeurer@chromium.org
Link to the patchset: https://codereview.chromium.org/2065243005/#ps80001
(title: "Remove static")

[commit-bot: I haz the power, 2016-06-29 14:29:22]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-06-29 14:54:57]

Description was changed from

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=
==========

to

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=
==========

[commit-bot: I haz the power, 2016-06-29 14:54:59]

Committed patchset #5 (id:80001)

[commit-bot: I haz the power, 2016-06-29 14:55:01]

CQ bit was unchecked.

[commit-bot: I haz the power, 2016-06-29 14:57:57]

Description was changed from

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=
==========

to

==========
[arm64] Generate adds/ands.

Perform the following transformation:

    | Before           | After               |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp w2, #0x0     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |
    |------------------+---------------------|
    | add w2, w0, w1   | adds w2, w0, w1     |
    | cmp #0x0, w2     | b.<cond'> <addr>    |
    | b.<cond> <addr>  |                     |

and the same for and instructions instead of add.  When the result of the
add/and is not used, generate cmn/tst instead. We need to take care with which
conditions we can handle and what new condition we map them to.

BUG=

Committed: https://crrev.com/317dc0578f21a7dd08568cbd802f6bf82b578591
Cr-Commit-Position: refs/heads/master@{#37400}
==========

[commit-bot: I haz the power, 2016-06-29 14:58:02]

Patchset 5 (id:??) landed as
https://crrev.com/317dc0578f21a7dd08568cbd802f6bf82b578591
Cr-Commit-Position: refs/heads/master@{#37400}