This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Use KnownBits for lshr/add -> (a + b < a)
Needs ReviewPublic

Authored by Pierre-vh on Jan 6 2023, 5:42 AM.

Details

Summary

Split from D138814; This patch allows any value for the add operands as long
as they have the right amount of leading zeroes.

Depends on D138814

Diff Detail

Event Timeline

Pierre-vh created this revision.Jan 6 2023, 5:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 6 2023, 5:42 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
Pierre-vh requested review of this revision.Jan 6 2023, 5:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 6 2023, 5:42 AM
Pierre-vh updated this revision to Diff 487362.Jan 9 2023, 2:56 AM

Add m_OneUse to match

spatel added inline comments.Jan 9 2023, 8:06 AM
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
846

Should that be "Only the K trailing bits..." or "The 'width - K' leading bits must be zero."?

Pierre-vh marked an inline comment as done.

Rebase, address comment

Forgot some changes

foad added inline comments.Jan 11 2023, 1:10 AM
llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
869–871

Should be '>' instead of '!=' surely? It would be fine if these values happen to have more leading zeros than required.

Pierre-vh updated this revision to Diff 488147.Jan 11 2023, 3:52 AM
Pierre-vh marked an inline comment as done.

Address comments

spatel added inline comments.Jan 12 2023, 8:25 AM
llvm/test/Transforms/InstCombine/shift-add.ll
510

Demanded bits should always zap cases like this.
A more interesting test would have just one side of the add with extra leading zeros:
https://alive2.llvm.org/ce/z/c4_YAE

So we'd be back to creating 2 extra instructions vs. the original sequence. That doesn't seem like a good trade-off in IR.

530

wrong hex value comment - 0xFFFF

arsenm added inline comments.Jan 12 2023, 8:25 AM
llvm/test/Transforms/InstCombine/shift-add.ll
530

There is a rarely used syntax to use hex constants in the IR but I never remember what it is

lebedev.ri requested changes to this revision.Jan 15 2023, 5:13 PM

(marking as reviewed)

llvm/test/Transforms/InstCombine/shift-add.ll
510

Presumably we can simply avoid that unprofitable case,
since e.g. lshr_16_add_known_16_leading_zeroes() looks like an improvement?

This revision now requires changes to proceed.Jan 15 2023, 5:13 PM
Pierre-vh marked 3 inline comments as done.

Comments

llvm/test/Transforms/InstCombine/shift-add.ll
510

It does removes it, not sure why it didn't there. Maybe I forgot to rebase?

spatel added inline comments.Jan 17 2023, 5:42 AM
llvm/test/Transforms/InstCombine/shift-add.ll
510

Yes - that seems like it would be ok; just restrict the pre-condition with ShAmt to equality (it was like that in an earlier draft?).

510

My comment might not have been clear:

  1. If both sides of the "add" have more leading zeros than the shift amount (the test as shown in this patch @lshr_16_add_known_17_leading_zeroes), we already reduce that "0" via SimplifyDemandedBits(). AFAIK, this patch does not change anything with an example like that.
  2. If only one side of the "add" has more leading zeros than the shift amount, then we probably can't get rid of the "and" mask by creating a "trunc". That's what I am seeing in the example I posted ( https://alive2.llvm.org/ce/z/c4_YAE ), and that's a test that I'd like to see included with this patch.
Pierre-vh updated this revision to Diff 493882.Feb 1 2023, 2:39 AM
Pierre-vh marked 2 inline comments as done.
  • Only allow == ShAmt
  • Add tests with 16/17 + 32/33 leading zeroes
spatel accepted this revision.Feb 3 2023, 9:15 AM

LGTM

@lebedev.ri can you please re-review? Thank you

@lebedev.ri please re-review - I can't land unless you approve the diff :)

nikic added a comment.Mar 1 2023, 6:03 AM

Would you mind pre-commit the new/update tests? The test diff is a bit hard to follow right now.

Do I understand right that we will replace two ands, one add and a lshr with two truncs, a uaddo and a zext? It's not super obvious that this is beneficial, but I guess the hope is that this will interact positively with other transforms (e.g. by pushing the trunc through operations and eliminating it entirely, or something)?

Pierre-vh updated this revision to Diff 501786.Mar 2 2023, 1:04 AM

We don't use uaddo but rather (a + b) < b. The intention is indeed to:

Initially we were using uaddo but it was decided to not have an intrinsic as a canonical form - I don't remember exactly why.

Pierre-vh updated this revision to Diff 514214.Apr 17 2023, 6:50 AM

Rebase + ping