This is an archive of the discontinued LLVM Phabricator instance.

[APInt] Rounding right-shifts
AbandonedPublic

Authored by lebedev.ri on Oct 8 2019, 4:33 PM.

Details

Summary

There's already rounding division, which is used in ConstantRange to
implement e.g. makeExactMulNUWRegion()/makeExactMulNUWRegion()
but there are no versions for right-shifts.
I'd like to try to extend ConstantRange::makeGuaranteedNoWrapRegion()
to deal with Instruction::Shl so i believe i need rounding right shifts.

The test coverage is confusing.
The existing RoundingSDiv() didn't actually pass - it never runs.
I've fixed that, and adjusted it to pass - i think we should be checking signed predicates?

Then i've added APIntOps::RoundingLShr(), APIntOps::RoundingAShr(),
standalone test coverage for them, and a cross-test to verify that
they produce identical output as compared to their div friends.
They do.

My understanding:

  • LShr is "dividing" by positive 2^shamt, so it rounds down. Since the operation is unsigned it also rounds towards zero.
    • (33 l>> 1) << 1 == 32
    • (-31 l>> 1) << 1 == -32

      Which means that if we want to round up, if there's remainder then we just need to always increment the quotent.
    • ((33 l>> 1) + 1) << 1 == 34
    • ((-31 l>> 1) + 1) << 1 == -30
  • AShr is "dividing" by positive 2^shamt, so it rounds down: (identical to LShr)
    • (33 a>> 1) << 1 == 32
    • (-31 a>> 1) << 1 == -32

      Again, if we want to round up, if there's remainder then we just need to always increment the quotent. (identical to LShr)
    • ((33 a>> 1) + 1) << 1 == 34
    • ((-31 a>> 1) + 1) << 1 == -30

      However, if we want to round towards zero, the behavior is different.
    • Since it's default behavior is to round down, then for positive numbers rounds towards zero is also the default:
      • (33 a>> 1) << 1 == 32
    • But for negatives by default we'd go away from zero:
      • (-31 l>> 1) << 1 == -32

        while the expected answer is -30; which is the answer for rounding up:
      • ((-31 a>> 1) + 1) << 1 == -30

        So if the value is negative then if quotent is non-zero - increment it, else do nothing.

Diff Detail

Event Timeline

lebedev.ri created this revision.Oct 8 2019, 4:33 PM
lebedev.ri marked an inline comment as done.
lebedev.ri added a subscriber: timshen.
lebedev.ri added inline comments.
llvm/unittests/ADT/APIntTest.cpp
2529–2538

@sanjoy @timshen FIXME: that's the intended check, right?

lebedev.ri updated this revision to Diff 223960.Oct 8 2019, 4:44 PM

Upload correct patch - i've meant to disable the RoundingSDiv test - it doesn't pass after making it actually run.

lebedev.ri edited the summary of this revision. (Show Details)Oct 9 2019, 3:17 AM
lebedev.ri edited the summary of this revision. (Show Details)
lebedev.ri updated this revision to Diff 224056.Oct 9 2019, 7:40 AM

Ok, last update - detect existence of quotent by counting trailing zeros, improve testss.

nikic added a comment.Oct 12 2019, 3:09 PM

I'd like to try to extend ConstantRange::makeGuaranteedNoWrapRegion()
to deal with Instruction::Shl so i believe i need rounding right shifts.

I don't think rounding shifts are strictly necessary for this purpose, the correct behavior should fall out when applying the normal lshr/ashr operations to -1 / signed_min / signed_max.

I'd like to try to extend ConstantRange::makeGuaranteedNoWrapRegion()
to deal with Instruction::Shl so i believe i need rounding right shifts.

I don't think rounding shifts are strictly necessary for this purpose,

the correct behavior should fall out when applying the normal lshr/ashr operations to -1 / signed_min / signed_max.

I'm not sure i can parse that, fall out?

I'm not sure i can parse that, fall out?

Sorry, what I meant is that the normal lshr/ashr will behave as desired for the purposes of determining a shl GNWR range. Something along the lines of...

case Instruction::Shl: {
  APInt UMax = Other.getUnsignedMax();
  unsigned MaxShift = Unsigned ? BitWidth - 1 : BitWidth - 2;
  if (UMax.uge(MaxShift)) // (An intersect would be more precise)
    return ConstantRange(APInt::getNullValue(BitWidth));
  if (Unsigned)
    return getNonEmpty(APInt::getNullValue(BitWidth),
                       APInt::getMaxValue(BitWidth).lshr(UMax) + 1);
  return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(UMax)
                     APInt::getSignedMaxValue(BitWidth).ashr(UMax) + 1);
}

We can still add these methods, they just don't seem necessary for the use-case you mentioned, unless I'm missing something.

I'm not sure i can parse that, fall out?

Sorry, what I meant is that the normal lshr/ashr will behave as desired for the purposes of determining a shl GNWR range. Something along the lines of...

case Instruction::Shl: {
  APInt UMax = Other.getUnsignedMax();
  unsigned MaxShift = Unsigned ? BitWidth - 1 : BitWidth - 2;
  if (UMax.uge(MaxShift)) // (An intersect would be more precise)
    return ConstantRange(APInt::getNullValue(BitWidth));
  if (Unsigned)
    return getNonEmpty(APInt::getNullValue(BitWidth),
                       APInt::getMaxValue(BitWidth).lshr(UMax) + 1);
  return getNonEmpty(APInt::getSignedMinValue(BitWidth).ashr(UMax)
                     APInt::getSignedMaxValue(BitWidth).ashr(UMax) + 1);
}

We can still add these methods, they just don't seem necessary for the use-case you mentioned, unless I'm missing something.

As i have discovered since then, it may make sense to first handle mul in CVP before looking into shifts.
So in this case it would be mainly good to have these for consistency.

Indeed, these turned out not to be needed for ConstanRange.
Do we want to have them for consistency regardless?

lebedev.ri abandoned this revision.Jan 25 2020, 3:29 AM