Selectively invert ICMP operands for better address optimization

Selectively invert ICMP operands for better address optimization

Results in lower code size and more loads folded into cmp instructions.

BUG=none
R=eholk@chromium.org, jpp@chromium.org, stichnot@chromium.org

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

[manasijm, 2016-07-07 20:38:10]

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

[John, 2016-07-07 21:20:56]

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode710
src/IceCfg.cpp:710: if (auto *ICMP = llvm::dyn_cast<InstIcmp>(&Inst)) {
optional: Icmp instead of ICMP

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode721
src/IceCfg.cpp:721: auto Op0Def =
getVMetadata()->getFirstDefinitionSingleBlock(Var0);
are you missing a * here?

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode722
src/IceCfg.cpp:722: if (!Op0Def || !llvm::isa<InstLoad>(Op0Def))
Op0Def == nullptr

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode726
src/IceCfg.cpp:726: 
optional: define Var1 here, closer to where it is used...

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode728
src/IceCfg.cpp:728: auto Op1Def =
getVMetadata()->getFirstDefinitionSingleBlock(Var1);
are you missing a * here?

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode735
src/IceCfg.cpp:735: switch (Cond) {
I would either add a "swap" field to the ICEINSTICMP_TABLE:


#define ICEINSTICMP_TABLE                  \
  /* enum value, swap, printable string */ \
  X(Eq,          Eq,   "eq")               \
  X(Ne,          Ne,   "ne")               \
  X(Ugt,         Ult,  "ugt")              \
  X(Uge,         Uge,  "uge")              \

and then define a table, or I would have a helper function:

namespace {
Icmp::ICond swap(Icmp::ICond cond) {
  switch (cond) {
    case Eq: return Eq;
    case Ne: return Ne;
  }
}
} // end of anonymous namespace

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.h#newcode205
src/IceCfg.h:205: void invertICMP();
This seems like X86-specific. If it is, then it should not live in IceCfg, but
in IceTargetLoweringX86Base

[Eric Holk, 2016-07-07 21:46:48]

lgtm otherwise (including fixing John's suggestions)

Both of my suggestions are about explicit comparisons with nullptr. I'm fine
either way (I actually prefer the implicit version), but it's best to follow the
rest of the code, which I think is to do explicit checks. I noticed a couple
other implicit checks that I didn't call out.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode713
src/IceCfg.cpp:713: if (Const0 || Const1)
Should this be (Const0 != nullptr || Const1 != nullptr), similarly to John's
comment on line 722?

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode717
src/IceCfg.cpp:717: if (!Var0)
Here too, Var0 == nullptr.

[manasijm, 2016-07-07 22:43:35]

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode710
src/IceCfg.cpp:710: if (auto *ICMP = llvm::dyn_cast<InstIcmp>(&Inst)) {
On 2016/07/07 21:20:56, John wrote:
> optional: Icmp instead of ICMP

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode713
src/IceCfg.cpp:713: if (Const0 || Const1)
On 2016/07/07 21:46:48, Eric Holk wrote:
> Should this be (Const0 != nullptr || Const1 != nullptr), similarly to John's
> comment on line 722?

Acknowledged.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode717
src/IceCfg.cpp:717: if (!Var0)
On 2016/07/07 21:46:48, Eric Holk wrote:
> Here too, Var0 == nullptr.

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode721
src/IceCfg.cpp:721: auto Op0Def =
getVMetadata()->getFirstDefinitionSingleBlock(Var0);
On 2016/07/07 21:20:56, John wrote:
> are you missing a * here?

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode722
src/IceCfg.cpp:722: if (!Op0Def || !llvm::isa<InstLoad>(Op0Def))
On 2016/07/07 21:20:55, John wrote:
> Op0Def == nullptr

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode726
src/IceCfg.cpp:726: 
On 2016/07/07 21:20:55, John wrote:
> optional: define Var1 here, closer to where it is used...

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode728
src/IceCfg.cpp:728: auto Op1Def =
getVMetadata()->getFirstDefinitionSingleBlock(Var1);
On 2016/07/07 21:20:55, John wrote:
> are you missing a * here?

Done.

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.cpp#newcode735
src/IceCfg.cpp:735: switch (Cond) {
Added a function to InstIcmp

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2124973005/diff/40001/src/IceCfg.h#newcode205
src/IceCfg.h:205: void invertICMP();
On 2016/07/07 21:20:56, John wrote:
> This seems like X86-specific. If it is, then it should not live in IceCfg, but
> in IceTargetLoweringX86Base

Found a nice place to move it.
Added a virtual function doAddressOptOther which is only implemented for X86. It
can be used as a general visitor to modify other instructions before load/store
opt.

[Jim Stichnoth, 2016-07-08 11:45:46]

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1090: case Eq:
I think this would be cleaner if you encode the invert values in the
ICEINSTICMP_TABLE x-macro table.

You could probably add it to InstIcmpAttributes[].

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.h#newcode553
src/IceInst.h:553: void invert();
How about invertCondition()?

Otherwise my default reading would be that it is supposed to "invert" the
*instruction*, which is less clear.

https://codereview.chromium.org/2124973005/diff/60001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:5656: return;
wat ?

https://codereview.chromium.org/2124973005/diff/60001/tests_lit/llvm2ice_test...
File tests_lit/llvm2ice_tests/address-mode-opt.ll (right):

https://codereview.chromium.org/2124973005/diff/60001/tests_lit/llvm2ice_test...
tests_lit/llvm2ice_tests/address-mode-opt.ll:195: foo:
I would name this something like "next" instead of "foo", just to make it read a
bit more serious.

[manasijm, 2016-07-08 18:11:40]

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1090: case Eq:
On 2016/07/08 11:45:46, stichnot wrote:
> I think this would be cleaner if you encode the invert values in the
> ICEINSTICMP_TABLE x-macro table.
> 
> You could probably add it to InstIcmpAttributes[].

Done.

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceInst.h#newcode553
src/IceInst.h:553: void invert();
On 2016/07/08 11:45:46, stichnot wrote:
> How about invertCondition()?
> 
> Otherwise my default reading would be that it is supposed to "invert" the
> *instruction*, which is less clear.

Done.

https://codereview.chromium.org/2124973005/diff/60001/src/IceTargetLoweringX8...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2124973005/diff/60001/src/IceTargetLoweringX8...
src/IceTargetLoweringX86BaseImpl.h:5656: return;
On 2016/07/08 11:45:46, stichnot wrote:
> wat ?

Sorry, remnant of testing with this turned off.

[John, 2016-07-08 18:21:08]

as long as Jim's happy, lgtm

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def
File src/IceInst.def (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def#newcode91
src/IceInst.def:91: /* enum value, inverse,  printable string */ \
this is not the inverse of the condition... I would probably use "invert" or
something else..

[Jim Stichnoth, 2016-07-10 13:25:32]

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1091: auto *TempOp = getSrc(0);
Since Srcs[] is a protected field that you have access to, how about just:

  std::swap(Srcs[0], Srcs[1]);

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def
File src/IceInst.def (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def#newcode91
src/IceInst.def:91: /* enum value, inverse,  printable string */ \
On 2016/07/08 18:21:08, John wrote:
> this is not the inverse of the condition... I would probably use "invert" or
> something else..

Yeah, I think I would agree.

My suggestion now is to call it "reverse", everywhere it was previous called
"inverse" or "invert".

Also, very minor nit.  Put only a single space after the comma in the comment -
multiple spaces are for when you want to align the comment fields with the
actual macro fields below.

Along those lines, slightly bigger nit.  Make the line-ending backslash
characters line up.  Since you're touching this file, you could also change all
backslash lines to put the backslash in column 80 like clang-format does,
instead of the weird indentation that emacs originally chose.

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.h#newcode553
src/IceInst.h:553: void invertConditionAndSwapOperands();
Per my comment in IceInst.def, I would rename this something like
reverseConditionAndOperands().  (If you use "reverse", I think you can omit
"swap" since it seems redundant.)

[manasijm, 2016-07-11 22:27:04]

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.cpp
File src/IceInst.cpp (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.cpp#newcode...
src/IceInst.cpp:1091: auto *TempOp = getSrc(0);
On 2016/07/10 13:25:32, stichnot wrote:
> Since Srcs[] is a protected field that you have access to, how about just:
> 
>   std::swap(Srcs[0], Srcs[1]);

Done.

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def
File src/IceInst.def (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.def#newcode91
src/IceInst.def:91: /* enum value, inverse,  printable string */ \
On 2016/07/10 13:25:32, stichnot wrote:
> On 2016/07/08 18:21:08, John wrote:
> > this is not the inverse of the condition... I would probably use "invert" or
> > something else..
> 
> Yeah, I think I would agree.
> 
> My suggestion now is to call it "reverse", everywhere it was previous called
> "inverse" or "invert".
> 
> Also, very minor nit.  Put only a single space after the comma in the comment
-
> multiple spaces are for when you want to align the comment fields with the
> actual macro fields below.
> 
> Along those lines, slightly bigger nit.  Make the line-ending backslash
> characters line up.  Since you're touching this file, you could also change
all
> backslash lines to put the backslash in column 80 like clang-format does,
> instead of the weird indentation that emacs originally chose.

Done.

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.h
File src/IceInst.h (right):

https://codereview.chromium.org/2124973005/diff/80001/src/IceInst.h#newcode553
src/IceInst.h:553: void invertConditionAndSwapOperands();
On 2016/07/10 13:25:32, stichnot wrote:
> Per my comment in IceInst.def, I would rename this something like
> reverseConditionAndOperands().  (If you use "reverse", I think you can omit
> "swap" since it seems redundant.)

Done.

[Jim Stichnoth, 2016-07-14 19:10:03]

https://codereview.chromium.org/2124973005/diff/100001/src/IceTargetLoweringX...
File src/IceTargetLoweringX86BaseImpl.h (right):

https://codereview.chromium.org/2124973005/diff/100001/src/IceTargetLoweringX...
src/IceTargetLoweringX86BaseImpl.h:5663: auto *Var0 =
llvm::dyn_cast<Variable>(Icmp->getSrc(0));
As we discussed offline, it seems like the conditions on Src0 and Src1 are (or
should be) essentially identical, so it would be nice to have a helper function
that is called twice.

We want to reverse the condition/operands when Src0 derives from a load
instruction, and Src1 does not derive from a load instruction.

[manasijm, 2016-07-15 20:25:50]

On 2016/07/14 19:10:03, stichnot wrote:
>
https://codereview.chromium.org/2124973005/diff/100001/src/IceTargetLoweringX...
> File src/IceTargetLoweringX86BaseImpl.h (right):
> 
>
https://codereview.chromium.org/2124973005/diff/100001/src/IceTargetLoweringX...
> src/IceTargetLoweringX86BaseImpl.h:5663: auto *Var0 =
> llvm::dyn_cast<Variable>(Icmp->getSrc(0));
> As we discussed offline, it seems like the conditions on Src0 and Src1 are (or
> should be) essentially identical, so it would be nice to have a helper
function
> that is called twice.
> 
> We want to reverse the condition/operands when Src0 derives from a load
> instruction, and Src1 does not derive from a load instruction.

Added a TODO, as discussed offline.

[Jim Stichnoth, 2016-07-20 22:25:57]

https://codereview.chromium.org/2124973005/diff/120001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2124973005/diff/120001/src/IceCfg.h#newcode206
src/IceCfg.h:206: void invertICMP();
Can this be removed?

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def
File src/IceInst.def (right):

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def#newcode34
src/IceInst.def:34: #define ICEINSTARITHMETIC_TABLE                             
                 \
The trailing \ should be in column 80 for consistency with what clang-format
does to .h/.cpp files.  These appear to be in column 79.

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def#newcode92
src/IceInst.def:92: X(Eq,  InstIcmp::ICond::Eq,  "eq")                          
               \
I think you should remove all the "InstIcmp::ICond::" prefixes, and apply it
(once) in IceInst.cpp.

[manasijm, 2016-07-20 22:54:17]

https://codereview.chromium.org/2124973005/diff/120001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/2124973005/diff/120001/src/IceCfg.h#newcode206
src/IceCfg.h:206: void invertICMP();
On 2016/07/20 22:25:56, stichnot wrote:
> Can this be removed?

Done.

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def
File src/IceInst.def (right):

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def#newcode34
src/IceInst.def:34: #define ICEINSTARITHMETIC_TABLE                             
                 \
On 2016/07/20 22:25:56, stichnot wrote:
> The trailing \ should be in column 80 for consistency with what clang-format
> does to .h/.cpp files.  These appear to be in column 79.

Done.

https://codereview.chromium.org/2124973005/diff/120001/src/IceInst.def#newcode92
src/IceInst.def:92: X(Eq,  InstIcmp::ICond::Eq,  "eq")                          
               \
On 2016/07/20 22:25:56, stichnot wrote:
> I think you should remove all the "InstIcmp::ICond::" prefixes, and apply it
> (once) in IceInst.cpp.

Done.

[Jim Stichnoth, 2016-07-21 01:39:00]

lgtm

[manasijm, 2016-07-21 19:40:26]

Description was changed from

==========
Selectively invert ICMP operands for better address optimization

Results in lower code size and more loads folded into cmp instructions.

BUG=none
==========

to

==========
Selectively invert ICMP operands for better address optimization

Results in lower code size and more loads folded into cmp instructions.

BUG=none
R=eholk@chromium.org, jpp@chromium.org, stichnot@chromium.org

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

[manasijm, 2016-07-21 19:40:28]

Committed patchset #8 (id:140001) manually as
0c70417672c2da35b06d121fc49e8bb6967e102e (presubmit successful).