Page MenuHomePhabricator

X86InstrInfo: Support immediates that are +1/-1 different in optimizeCompareInstr
AcceptedPublic

Authored by MatzeB on Thu, Sep 30, 11:19 AM.

Details

Summary

This extends optimizeCompareInstr to re-use previous comparison results if the previous comparison was with an immediate that was 1 bigger or smaller. Example:

CMP x, 13
...
CMP x, 12   ; can be removed if we change the SETg
SETg ...    ; x > 12  changed to `SETge` (x >= 13) removing CMP

Motivation: This often happens because SelectionDAG canonicalization tends to add/subtract 1 often when optimizing for fallthrough blocks. Example for x > C the fallthrough optimization switches true/false blocks with !(x > C) --> x <= C and canonicalization turns this into x < C + 1.

Diff Detail

Event Timeline

MatzeB created this revision.Thu, Sep 30, 11:19 AM
MatzeB requested review of this revision.Thu, Sep 30, 11:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Sep 30, 11:19 AM
MatzeB edited the summary of this revision. (Show Details)Thu, Sep 30, 11:33 AM
foad added a subscriber: foad.Fri, Oct 1, 6:20 AM
foad added inline comments.
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

Is it OK to use INT64_MIN >> Shift here? I think the standard says right shift of a negative value is implementation-defined.

MatzeB marked an inline comment as done.Fri, Oct 1, 10:00 AM
MatzeB added inline comments.
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

Good question!

I think we can rely on two-complement arithmetic shift behavior here. I'm not aware of any compiler behaving differently, certainly not the one ones specified to be used for LLVM in the documentation: https://llvm.org/docs/GettingStarted.html#host-c-toolchain-both-compiler-and-standard-library

Other code like APInt seems to rely on this as well: https://github.com/llvm/llvm-project/blob/4f0225f6d21b601d62b73dce913bf59d8fb93d87/llvm/include/llvm/ADT/APInt.h#L796

That said if you have a simple alternative to this, I'd be happy to change the code...

MatzeB marked an inline comment as done.Fri, Oct 1, 10:04 AM
MatzeB added inline comments.Fri, Oct 1, 10:11 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

How about I add this:

static_assert(INT64_MIN >> 16 == INT32_MIN && INT64_MIN >> 24 == INT8_MIN,
              "expects compiler with twos complement right shift");

and then whoever has a whacky compiler will see the problem and can go fix it.

foad added inline comments.Fri, Oct 1, 10:20 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

I was mostly worried a buildbot with the "undefined behaviour" sanitiser complaining about it -- though I'm not actually sure if ubsan detects this by default.

I don't really mind what fix you use, if any. The static_assert sounds fine to me. Alternatively you could rewrite the expression, e.g. as ~(INT64_MAX >> Shift), but it's much less obvious what it means.

MatzeB updated this revision to Diff 376576.Fri, Oct 1, 11:02 AM
xbolva00 added inline comments.
llvm/test/CodeGen/X86/jump_sign.ll
133 ↗(On Diff #376576)

cmp now removed

RKSimon added inline comments.Thu, Oct 14, 2:51 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

What about using APInt?

MatzeB added inline comments.Thu, Oct 14, 10:42 AM
llvm/test/CodeGen/X86/jump_sign.ll
133 ↗(On Diff #376576)

Good catch. So:

  • I believe the comment to be outdated:
  • The new version of the code is correct; you see that previously it used a cmpl ecx, edx, but edx and eax contain the same value and the sub in bb.0 the only predecessor of bb.1 is just the reverse operation and will produce the reverse flags. So we can indeed remove the cmp when we reverse the user flags cmovle -> cmovl.
  • I accidentally put this test change onto the wrong commit in the stack. The test actually changes in D110862.
MatzeB added inline comments.Thu, Oct 14, 11:01 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

What about using APInt?

Seemed a bit overengineered given the value fits neatly in an uint64_t, but sure I will change it to use an APInt then.

MatzeB added inline comments.Thu, Oct 14, 11:02 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4496

Or let me factor out a common helper to shift an uint64_t that we can use in APInt and here.

MatzeB updated this revision to Diff 379823.Thu, Oct 14, 1:35 PM

rebase; use APInt to compute maximum/minimum constants.

foad added inline comments.Fri, Oct 15, 12:24 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4495

Surely you need APInt::getSignedMinValue(BitWidth)?

MatzeB added inline comments.Fri, Oct 15, 11:02 AM
llvm/lib/Target/X86/X86InstrInfo.cpp
4495

Good point. Changed them now.

I just realized that technically this check isn't necessary as the tests I added still pass. This is because the ImmDelta calculations are actually done on int64_t values so they don't wrap around for 8/16/32 bit immediates and instead just overflow to an unrepresentable immediate. We would have overflow problems for 64bit immediates, but x86 doesn't support those.

Anyway I think I'll keep the tests here anyway as I like the expressed intent, and if someone ever introduces a 64bit immediates we are prepared :)

MatzeB updated this revision to Diff 380064.Fri, Oct 15, 11:03 AM
MatzeB updated this revision to Diff 380065.
RKSimon accepted this revision.Sat, Oct 16, 2:35 AM

LGTM - cheers

This revision is now accepted and ready to land.Sat, Oct 16, 2:35 AM