This is an archive of the discontinued LLVM Phabricator instance.

[KnownBits] Improve `KnownBits::rem(X, Y)` in cases where we can deduce low-bits of output
ClosedPublic

Authored by goldstein.w.n on Apr 27 2023, 11:22 PM.

Details

Summary

The first cttz(Y) bits in X are translated 1-1 in the output.

Alive2 Links:

https://alive2.llvm.org/ce/z/Qc47p7
https://alive2.llvm.org/ce/z/19ut5H

Diff Detail

Event Timeline

goldstein.w.n created this revision.Apr 27 2023, 11:22 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 27 2023, 11:22 PM
goldstein.w.n requested review of this revision.Apr 27 2023, 11:22 PM
foad added a comment.Apr 28 2023, 3:34 AM

Looks reasonable overall.

llvm/lib/Support/KnownBits.cpp
552

Missing word after "will"?

554

Use getLowBitsSet?

557

We already checked !LHS.hasConflict() in both callers so this seems unnecessary to me.

580

Just a matter of taste, but I'd prefer to write this as Known |= remGetLowBits(LHS, RHS);.

Also could move this above the RHS.isConstant case - then that case would only need to handle setting the high bits of Known.Zero.

llvm/test/Analysis/ScalarEvolution/merge-add-rec-many-inputs.ll
1 ↗(On Diff #517805)

Looks like a spurious change?

goldstein.w.n marked 4 inline comments as done.Apr 28 2023, 9:19 AM
goldstein.w.n added inline comments.
llvm/lib/Support/KnownBits.cpp
580

Just a matter of taste, but I'd prefer to write this as Known |= remGetLowBits(LHS, RHS);.

I don't think this is right. KnowBits::| does Known.Zero &= remGetLowBits.Zero. We want the opposite. If some of the lowbits of X are zero in this case, we want to forcefully set those bits in Known.

Also could move this above the RHS.isConstant case - then that case would only need to handle setting the high bits of Known.Zero.

sure.

Remove spurios change, move before const case, little cleanup

foad added inline comments.Apr 28 2023, 9:22 AM
llvm/lib/Support/KnownBits.cpp
580

I don't think this is right.

Good point. You'd want some kind of "merge" operation which doesn't exist because I can't think of a good name for it.

foad added inline comments.Apr 28 2023, 9:27 AM
llvm/lib/Support/KnownBits.cpp
568–572

New suggestion: simplify this to KnownBits Known = remGetLowBits(LHS, RHS);

goldstein.w.n added inline comments.Apr 28 2023, 10:29 AM
llvm/lib/Support/KnownBits.cpp
568–572

Any objections to pass Known to remGetLowBits as const-ref? Don't want to force the assumption that remGetLowBits is called before any other bits are set.

How about:

KnownBits remGetLowBits(const KnownBits &Known, const KnownBits &LHS,
                          const KnownBits &RHS);

Passing with &for mutability is always an odd pattern.

How about:

KnownBits remGetLowBits(const KnownBits &Known, const KnownBits &LHS,
                          const KnownBits &RHS);

Passing with &for mutability is always an odd pattern.

Agreed and done.

Remove mutable reference

goldstein.w.n added inline comments.Apr 28 2023, 12:24 PM
llvm/lib/Support/KnownBits.cpp
580

I don't think this is right.

Good point. You'd want some kind of "merge" operation which doesn't exist because I can't think of a good name for it.

How about "merge"? XD

RKSimon added a reviewer: RKSimon.EditedApr 29 2023, 10:21 AM
RKSimon added a subscriber: RKSimon.
This comment has been deleted.
RKSimon added inline comments.May 3 2023, 9:22 AM
llvm/lib/Support/KnownBits.cpp
549

Do we need Known?

goldstein.w.n added inline comments.May 3 2023, 10:14 AM
llvm/lib/Support/KnownBits.cpp
549

Yeah. We don't have a "merge" function (to take known results from A and apply them to B).
There was a bit of conversation below (around L580) about it.

RKSimon added inline comments.May 3 2023, 10:25 AM
llvm/lib/Support/KnownBits.cpp
549

But do we need a merge? All the calls to remGetLowBits are at the start when Known is empty

goldstein.w.n added inline comments.May 3 2023, 10:34 AM
llvm/lib/Support/KnownBits.cpp
549

Oh yeah. My feeling there was the API should work on arbitrary state, not just init state. Otherwise just seems like a bug waiting to happen.

nikic added inline comments.May 3 2023, 11:03 AM
llvm/lib/Support/KnownBits.cpp
549

As this is a private API, I don't think there's a need to generalize it to a use case that currently doesn't exist...

goldstein.w.n added inline comments.May 3 2023, 11:10 AM
llvm/lib/Support/KnownBits.cpp
549

Private API to users sure, if in a year if someone add some improvement will it be clear? To me it seems like basically zero cost to passing Known and potential cost in not doing so. If you're not convinced, however, (either of you), ill change. LMK.

foad added inline comments.May 3 2023, 12:14 PM
llvm/lib/Support/KnownBits.cpp
549

I much prefer not passing in Known.

goldstein.w.n marked an inline comment as done.May 3 2023, 1:56 PM
goldstein.w.n added inline comments.
llvm/lib/Support/KnownBits.cpp
549

Okay done :)

goldstein.w.n marked an inline comment as done.

Remove known as arg

foad added inline comments.May 4 2023, 1:27 AM
llvm/lib/Support/KnownBits.cpp
599–600

Remove this line too.

nikic added inline comments.May 4 2023, 1:31 AM
llvm/lib/Support/KnownBits.cpp
575

You can drop the KnownOut variable here and just use Known.

KnownBitsTest has an exhaustive test for srem and urem - so the likelihood of bugs surfacing are pretty low.

llvm/lib/Support/KnownBits.cpp
578

return KnownBits(ZerosMask, OnesMask)

580

return KnownBits(BitWidth)

goldstein.w.n added inline comments.May 4 2023, 9:00 AM
llvm/lib/Support/KnownBits.cpp
599–600

Why? Isn't it a bit confusing that we only set zeros?

KnownBitsTest has an exhaustive test for srem and urem - so the likelihood of bugs surfacing are pretty low.

I'm less worried about a correctness failure. Moreso undoing information we could have deduced with unknown state.

goldstein.w.n marked 3 inline comments as done.May 4 2023, 9:39 AM
goldstein.w.n added inline comments.
llvm/lib/Support/KnownBits.cpp
578

Sure, although this is private so need to put this function in the class then.

goldstein.w.n marked an inline comment as done.

Cleanup helper now that it returns init state

RKSimon accepted this revision.May 4 2023, 9:48 AM

LGTM with a minor

llvm/lib/Support/KnownBits.cpp
574

// NB: Low one bits set in remGetLowBits

597

// NB: Low one bits set in remGetLowBits

This revision is now accepted and ready to land.May 4 2023, 9:48 AM
foad added inline comments.May 5 2023, 12:20 AM
llvm/lib/Support/KnownBits.cpp
599–600

I'm saying you should remove Known.Zero = LHS.Zero & LowBits, because it has already been done by remGetLowBits. The only extra stuff we need to do in the constant RHS case is to do the high bits.

goldstein.w.n marked an inline comment as done.

Also use for low-zeros

This revision was landed with ongoing or failed builds.May 7 2023, 5:12 PM
This revision was automatically updated to reflect the committed changes.
foad added inline comments.May 12 2023, 5:47 AM
llvm/lib/Support/KnownBits.cpp
580

How about "merge"? XD

Great idea! But here's what I came up with: D150443