This is an archive of the discontinued LLVM Phabricator instance.

[KnownBits] Add computeForAddCarry()
ClosedPublic

Authored by nikic on Apr 10 2019, 11:13 AM.

Details

Summary

This is for D60460. computeForAddSub() essentially already supports carries because it has to deal with subtractions. This revision extracts a lower-level computeForAddCarry() function, which allows computing the known bits for add (carry known zero), sub (carry known one) and addcarry (carry unknown).

As we don't seem to have any yet, I've added a unit test file for KnownBits and an exhaustive test for the computeForAddCarry functionality.

Diff Detail

Repository
rL LLVM

Event Timeline

nikic created this revision.Apr 10 2019, 11:13 AM
lebedev.ri added inline comments.Apr 10 2019, 12:38 PM
llvm/lib/Support/KnownBits.cpp
20–21 ↗(On Diff #194548)

How about simply making it KnownBits(/*KnownBits=*/1) ?

nikic marked an inline comment as done.Apr 10 2019, 1:17 PM
nikic added inline comments.
llvm/lib/Support/KnownBits.cpp
20–21 ↗(On Diff #194548)

It's a possibility, but I'm not convinced it's better here. The booleans directly enforce the contract that this is just one bit (while for KnownBits we could only assert that), they're cheaper to construct and use than two APInts, and the API is simpler to use, because we don't have to construct KnownBits (which is somewhat roundabout due to lack of a direct ctor).

I think the only place that would really benefit from passing carry as KnownBits is the testing code, while for other usages having this as booleans is more convenient and efficient.

RKSimon added inline comments.Apr 11 2019, 1:44 AM
llvm/lib/Support/KnownBits.cpp
35 ↗(On Diff #194548)

Are we gaining much from using the std::move? It reduces grokability and in most cases we'll be dealing with APInts representing i64 or less so its not heap allocated.

llvm/unittests/Support/KnownBitsTest.cpp
49 ↗(On Diff #194548)

AddCarryExhaustive

bjope added inline comments.Apr 11 2019, 2:02 AM
llvm/lib/Support/KnownBits.cpp
20–21 ↗(On Diff #194548)

If we want to also track the carry in the future I guess we would get that as a "KnownBits".

So I think that for ADDCARRY we probably want to do

KnownBits KnownLHS = computeKnownBits(Op.getOperand(0), DemandedElts, Depth + 1);
KnownBits KnownRHS = computeKnownBits(Op.getOperand(1), DemandedElts, Depth + 1);
KnownBits KnownCarry = computeKnownBits(Op.getOperand(2), DemandedElts, Depth + 1);
Known = computeForAddCarry(KnownLHS, KnownRHS, KnownCarry.trunc(1));

if we also want to also track down the known bits of the carry.

So having a computeForAddCarry method that takes a KnownBits(1) might actually be useful (compared to trying to convert KnownCarry into two booleans on the user side of this API). If there is a use for also having the bool based interface, then perhaps we can have both?

nikic updated this revision to Diff 194650.Apr 11 2019, 2:23 AM

Use KnownBits for carry in exported API, fix typo in test name.

nikic marked 2 inline comments as done.Apr 11 2019, 2:26 AM
nikic added inline comments.
llvm/lib/Support/KnownBits.cpp
20–21 ↗(On Diff #194548)

That's a good point. I've changed the implementation to use a 1-bit KnownBits in the exported API. The variant that uses two booleans is now only used internally to shared between the exported computeForAddCarry and computeForAddSub APIs.

nikic marked an inline comment as done.Apr 11 2019, 9:11 AM
nikic added a subscriber: craig.topper.
nikic added inline comments.
llvm/lib/Support/KnownBits.cpp
35 ↗(On Diff #194548)

The use of std::move() in this code was introduced as part of D36433. Maybe @craig.topper could comment?

bjope added a comment.Apr 12 2019, 4:56 AM

LGTM! (with a nit in the test case)

I also think we should consider to add more exhaustive tests for computeForAddSub, now when we got the unittest support from this patch.

llvm/unittests/Support/KnownBitsTest.cpp
1 ↗(On Diff #194650)

nit: KnownBitsTest.cpp

48 ↗(On Diff #194650)

The patch slightly touches the computeForAddSub implementation. So even if it can be seen as unrelated, maybe we should add a exhaustive test for computeForAddSub as well. Shouldn't be too hard given this framework, or what do you think?

nikic updated this revision to Diff 194859.Apr 12 2019, 6:23 AM

Fix file name, add tests for computeForAddSub().

nikic updated this revision to Diff 194866.Apr 12 2019, 6:35 AM
nikic marked 2 inline comments as done.

Also test NSW flag.

lebedev.ri accepted this revision.Apr 12 2019, 6:41 AM

LG modulo nits, if @RKSimon has no further comments.

llvm/lib/Support/KnownBits.cpp
18 ↗(On Diff #194859)

The signature is already different from computeForAddCarry() (2 bools vs 1 KnownBits),
i don't see the need for Internal suffix.
Also, i believe anonymous namespaces are preferred, so drop static, and wrap into namespace {}.

54 ↗(On Diff #194859)

All these bool params are potential bugs, and really affect readability.
But i guess that would be too intrusive for this header.

This revision is now accepted and ready to land.Apr 12 2019, 6:41 AM
nikic marked an inline comment as done.Apr 12 2019, 7:00 AM
nikic added inline comments.
llvm/lib/Support/KnownBits.cpp
18 ↗(On Diff #194859)

Agree on the suffix being unnecessary. Regarding anonymous namespaces, https://llvm.org/docs/CodingStandards.html#anonymous-namespaces says:

Because of this, we have a simple guideline: make anonymous namespaces as small as possible, and only use them for class declarations.

If I'm understanding correctly, this means that anon namespaces should be used for classes and static for functions.

RKSimon accepted this revision.Apr 12 2019, 7:04 AM

LGTM - let's leave the std::move issue for now

lebedev.ri marked an inline comment as done.Apr 12 2019, 8:11 AM
lebedev.ri added inline comments.
llvm/lib/Support/KnownBits.cpp
18 ↗(On Diff #194859)

If I'm understanding correctly, this means that anon namespaces should be used for classes and static for functions.

There have been discussions about exactly that recently, in other reviews.
So i'm not confident what is currently considered as the best common practice for functions.

nikic marked 2 inline comments as done.Apr 12 2019, 8:52 AM
nikic added inline comments.
llvm/lib/Support/KnownBits.cpp
18 ↗(On Diff #194859)

I'd prefer to leave this as a static function for now -- if there's interest in changing the recommended practice around this it should imho start with a patch to CodingStandards.

54 ↗(On Diff #194859)

We might want to start a separate file outside Support (I'm thinking llvm/Analysis/KnownBitsOps.h and lib/Analysis/KnownBitsOps.cpp) that can depend on things like binop opcodes and obo flags and allow sharing more of the KnownBits code between ValueTracking and SDAG. The existing KnownBits header mostly has only primitive operations and is quite cumbersome to edit (because it rebuilds half of LLVM).

lebedev.ri added inline comments.Apr 12 2019, 10:23 AM
llvm/lib/Support/KnownBits.cpp
54 ↗(On Diff #194859)

Sorry, there was another phrase between those two i posted:

All these bool params are potential bugs, and really affect readability.

"i'd prefer to pass them as some enum fields, e.g. the ones used elsewhere in IR for IR instructions and wrap flags"

But i guess that would be too intrusive for this header.

But yes, i guess it will be best to reinvent the wheel here, and add whole new enum.

This revision was automatically updated to reflect the committed changes.