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

[nikic]

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).

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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]

llvm/lib/Analysis/ValueTracking.cpp

4192–4194 ↗

(On Diff #191024)

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

[spatel]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

4185–4186 ↗

(On Diff #191024)

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.

[lebedev.ri]

Great, i'm ok with this too.

llvm/trunk/lib/Analysis/ValueTracking.cpp

static OverflowResult computeOverflowForSignedAdd(const Value *LHS,
   if (OR != OverflowResult::MayOverflow)
     return OR;
 
   // The remaining code needs Add to be available. Early returns if not so.
   if (!Add)
     return OverflowResult::MayOverflow;
 
   // If the sign of Add is the same as at least one of the operands, this add
-  // CANNOT overflow. This is particularly useful when the sum is
-  // @llvm.assume'ed non-negative rather than proved so from analyzing its
-  // operands.
+  // CANNOT overflow. If this can be determined from the known bits of the
+  // operands the above signedAddMayOverflow() check will have already done so.
+  // The only other way to improve on the known bits is from an assumption, so
+  // call computeKnownBitsFromAssume() directly.
   bool LHSOrRHSKnownNonNegative =
       (LHSKnown.isNonNegative() || RHSKnown.isNonNegative());
   bool LHSOrRHSKnownNegative =
       (LHSKnown.isNegative() || RHSKnown.isNegative());
   if (LHSOrRHSKnownNonNegative || LHSOrRHSKnownNegative) {
-    KnownBits AddKnown = computeKnownBits(Add, DL, /*Depth=*/0, AC, CxtI, DT);
+    KnownBits AddKnown(LHSKnown.getBitWidth());
+    computeKnownBitsFromAssume(
+        Add, AddKnown, /*Depth=*/0, Query(DL, AC, CxtI, DT, true));
     if ((AddKnown.isNonNegative() && LHSOrRHSKnownNonNegative) ||
-        (AddKnown.isNegative() && LHSOrRHSKnownNegative)) {
+        (AddKnown.isNegative() && LHSOrRHSKnownNegative))
       return OverflowResult::NeverOverflows;
-    }
-  }
 
   return OverflowResult::MayOverflow;
 }
 
 OverflowResult llvm::computeOverflowForUnsignedSub(const Value *LHS,
                                                    const Value *RHS,
                                                    const DataLayout &DL,
                                                    AssumptionCache *AC,