This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Avoid redundant known bits calculation in computeOverflowForSignedAdd()
ClosedPublic

Authored by nikic on Mar 17 2019, 9:29 AM.

Details

Summary

This is a tangent to D59386, which got me thinking about the performance of this code...

We're already computing the known bits of the operands here. If the known bits of the operands can determine the sign bit of the result, we'll already catch this in the ripple logic. The only other way (and as the comment already indicates) we'll get new information from computing known bits on the whole add, is if there's an assumption on it.

As such, we change the code to only compute known bits from assumptions, instead of computing full known bits on the add (which would unnecessarily recompute the known bits of the operands as well).

Diff Detail

Event Timeline

nikic created this revision.Mar 17 2019, 9:29 AM
lebedev.ri added inline comments.Mar 17 2019, 2:19 PM
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

What about this comment in computeKnownBits():

// computeKnownBitsFromAssume strictly refines Known.
// Therefore, we run them after computeKnownBitsFromOperator.

By looking at computeKnownBitsFromAssume(), it doesn't look like that will affect the correctness of output,
the bits that weren't inferred from assumption will simply remain unknown, correct?

nikic marked an inline comment as done.Mar 17 2019, 2:41 PM
nikic added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

That's right. computeKnownBitsFromAssume() ORs in any additional known bits it can determine. With the computeKnownBits() call it would start off from the computeKnownBitsFromOperator() bits, while with the direct call here it will start off with no known bits.

lebedev.ri added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

Ok, so that is how i understood,
That is sound to me, but i wonder if we can rely on that behavior.

lebedev.ri added inline comments.Mar 17 2019, 2:57 PM
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

Wait, how do you even use computeKnownBitsFromAssume() here, it is a static function in ValueTracking.cpp?

lebedev.ri added inline comments.Mar 17 2019, 3:16 PM
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

... because we are in the ValueTracking.cpp, right, enough for today.
But the other question remains.

nikic marked an inline comment as done.Mar 20 2019, 11:22 AM
nikic added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

That is sound to me, but i wonder if we can rely on that behavior.

I think so. Or rather: I don't think it really matters either way. While this function will add in additional information, many other functions that accept KnownBits just overwrite it entirely. In this case both behaviors would get us the same result, as our starting state is "nothing known".

lebedev.ri added inline comments.Mar 21 2019, 5:29 AM
llvm/lib/Analysis/ValueTracking.cpp
4192–4194

This does sound good to me, but i would like for other reviewers to comment on this.

LGTM

llvm/lib/Analysis/ValueTracking.cpp
4185–4186

Let's make this comment include more of the description/discussion from this review, so we have it inline in the code. So add something like:
We already calculated the known bits of each operand and checked for ripple. The only other way to improve on the known bits is from an assumption, so call that directly.

spatel accepted this revision.Mar 22 2019, 9:57 AM
This revision is now accepted and ready to land.Mar 22 2019, 9:57 AM
lebedev.ri accepted this revision.Mar 22 2019, 10:06 AM

Great, i'm ok with this too.

This revision was automatically updated to reflect the committed changes.