Page MenuHomePhabricator

[SelectionDAG] Use KnownBits::computeForAddSub in SelectionDAG::computeKnownBits
ClosedPublic

Authored by bjope on Apr 9 2019, 6:26 AM.

Details

Summary

Start using KnownBits::computeForAddSub in
SelectionDAG::computeKnownBits when doing value
tracking for addition/subtraction.

This should improve the precision of the known bits,
as we only used to make a simple estimate of known
zeroes. The KnownBits::computeForAddSub function is
also able to deduce bits that are known to be one
in the result.

Diff Detail

Repository
rL LLVM

Event Timeline

bjope created this revision.Apr 9 2019, 6:26 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 9 2019, 6:27 AM
Herald added a subscriber: hiraditya. · View Herald Transcript

This looks ok, but should have more tests.

llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2971–2974 ↗(On Diff #194305)

When committing, this should/could be a separate change.

2986 ↗(On Diff #194305)

This is correct, what llvm::haveNoCommonBitsSet() does.

bjope updated this revision to Diff 194385.Apr 9 2019, 1:05 PM

Added a unittest (by using the AArch64SelectionDAGTest unittest framework).

nikic added a subscriber: nikic.Apr 9 2019, 1:20 PM

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

Hmm, good point. In general because of IR Value vs DAG SDValue. But clearly that function should work here..

bjope added a comment.Apr 10 2019, 1:21 AM

We have an accurate known bits implementation for adds in KnownBits::computeForAddSub(), which should handle this and more automatically. We use it to compute add known bits in IR. Is there a reason why it's not used for SDAG known bits?

Hmm, good point. In general because of IR Value vs DAG SDValue. But clearly that function should work here..

Ahh, great! Using KnownBits::computeForAddSub() sounds like the right thing to do. I'll give it a try!

And then I guess we should do the same for SUB. I need to figure out if the computeForAddSub cover the special cases handled by SelectionDAG for SUB. I might skip doing anything about SUB in this patch if it turns out to be non-trivial to simply replace the current logic with a call to computeForAddSub.

bjope updated this revision to Diff 194468.Apr 10 2019, 2:37 AM

Use KnownBits::computeForAddSub instead, and do it for both ADD* and SUB* nodes.

bjope retitled this revision from [SelectionDAG] Let computeKnownBits handle OR-like ADDs better to [SelectionDAG] Use KnownBits::computeForAddSub in SelectionDAG::computeKnownBits.Apr 10 2019, 2:38 AM
bjope edited the summary of this revision. (Show Details)
bjope added reviewers: nikic, lebedev.ri.
nikic added inline comments.Apr 10 2019, 2:56 AM
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2948 ↗(On Diff #194468)

I think it would make more sense to move the computeForAddSub calculation above this branch, and then do something like this here:

// With ADDE and ADDCARRY a carry bit may be added, so we can only use
// this information if we know that the low bit is clear.
if (!lowBitSet(Known.Zero)) { // How do you write this operation with APInt?
  Known.One.clearAllBits();
  Known.Zero.clearAllBits();
  break;
}

Known.Zero.clearBit(0);

This allows us to use the full known bits result, just without the low bit, if it is possible.

RKSimon added inline comments.Apr 10 2019, 3:00 AM
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2911 ↗(On Diff #194468)

No need to construct KnownLHS here
KnownBits KnownLHS = computeKnownBits
(or we could add a Known3 to the top of the function?)

2933 ↗(On Diff #194468)

KnownBits KnownLHS = computeKnownBits

bjope added inline comments.Apr 10 2019, 4:45 AM
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2948 ↗(On Diff #194468)

Or maybe I can use computeForAddSub a second time, simulating an add of the carry bit

// With ADDE and ADDCARRY, a carry bit may be added in.
if (Opcode == ISD::ADDE || Opcode == ISD::ADDCARRY) {
  // TODO: Can we compute known bits for the carry bit? For now we set it to
  // unknown.
  Known2.setAllZero();
  Known2.Zero.clearBit(0);
  Known = KnownBits::computeForAddSub(/* IsAdd */ true, /* NSW */ false,
                                      Known, Known2);
}
bjope updated this revision to Diff 194497.Apr 10 2019, 5:20 AM

Simplified based on feedback.

nikic added inline comments.Apr 10 2019, 11:24 AM
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2948 ↗(On Diff #194468)

This works and is fully accurate. I think it would be slightly better to integrate the carry in the computeForAddSub() calculation, because it's cheaper than doing it twice. I've opened D60522 to support this. With this method the implementation here would reduce to:

bool CarryKnownZero = Opcode != ISD::ADDE && Opcode != ISD::ADDCARRY;
Known = KnownBits::computeForAddCarry(
    Known, Known2, CarryKnownZero, /*CarryKnownOne*/ false);
bjope marked an inline comment as done.Apr 11 2019, 2:19 AM
bjope added inline comments.
llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
2929 ↗(On Diff #194497)

Am I missing something, or isn't ADDC and ADDE producing multiple results (just like ADDCARRY etc above)?
So isn't it necessary to check if we are tracking the result of getResNo()==0 or getResNo()=1 also for ADDC and ADDE?

bjope updated this revision to Diff 194701.Apr 11 2019, 8:47 AM

Updated to use a KnownBits::computeForAddCarry helper. I added a simple
implementation here, but the idea is to replace it by the improved version
from D60522 instead (if we land that patch before this one).

Also added a TODO for computing known bits for the carry in ADDCARRY. If we do
not think it is worth the trouble I can remove the TODO again before landing
this.
It is probably more important to add known bits tracking for the non-carry
result produced SUBCARRY (as we can rewrite ADDCARRY into SUBCARRY which at
the moment results in losing info about known bits).

lebedev.ri added inline comments.Apr 12 2019, 8:17 AM
llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp
160 ↗(On Diff #194701)

If a diff is based on some other patch, it is best not to include that other patch into this diff (be more specific for which commits you want to generate the diff in git), but instead mark that other patch as parent.

bjope added inline comments.Apr 12 2019, 8:30 AM
llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp
160 ↗(On Diff #194701)

Not sure if I get that. You asked for test cases, and these are the test cases I added (they would fail without the improvements in computeKnownBits for ADD and SUB).

Although, I see now that I made a typo in the test names. They should be called ComputeKnownBits_ADD and ComputeKnownBits_SUB.

However, if I rebase this upon https://reviews.llvm.org/D60522 this patch will use the helpers in KnownBits (which also includes more exhaustive unittests). So I guess these tests will become less important after that rebase.

161 ↗(On Diff #194701)

typo: ComputeKnownBits_ADD

182 ↗(On Diff #194701)

typo: ComputeKnownBits_SUB

bjope marked an inline comment as done.Apr 12 2019, 8:31 AM
bjope added inline comments.
llvm/test/CodeGen/X86/x32-va_start.ll
62 ↗(On Diff #194701)

The patch with CopyFromReg has been reverted. So this diff will go away after rebasing to trunk.

bjope marked 5 inline comments as done.Apr 12 2019, 9:31 AM

(Yes, i think it is best to rebase this ontop of D60522.)

llvm/unittests/CodeGen/AArch64SelectionDAGTest.cpp
160 ↗(On Diff #194701)

Not sure if I get that.

Oh sorry, i quickly looked over this, and though this was already based on D60522 *AND* included it's testcases here.
All good.

Rebase now that D60522 landed?

bjope updated this revision to Diff 194960.Apr 12 2019, 2:06 PM

Rebased. Corrected typos in the test cases.

bjope marked 2 inline comments as done.Apr 12 2019, 2:07 PM
nikic accepted this revision.Apr 14 2019, 3:48 AM

LGTM

This revision is now accepted and ready to land.Apr 14 2019, 3:48 AM
This revision was automatically updated to reflect the committed changes.