[APInt] Merge the multiword code from lshrInPlace and tcShiftRight into a single implementation

[craig.topper]

Summary

This merges the two different multiword shift right implementations into a single version located in tcShiftRight. lshrInPlace now calls tcShiftRight for the multiword case.

I retained the memmove fast path from lshrInPlace and used a memset for the zeroing. The for loop is basically tcShiftRight's implementation with the zeroing and the intra-shift of 0 removed.

[craig.topper]

Fix diff context

[hans]

lgtm with a naming suggestion

Are there tests covering this? I couldn't find any direct tests, but are there at least indirect ones that would break if for example you change the function to not shift at all?

Do we have the same situation with tcShiftLeft and shlSlowCase? I suppose it's not quite the same since shlSlowCase isn't in-place, but maybe there's some code to be shared anyway?

lib/Support/APInt.cpp

2690

Hmm, seems it's spelled COUNT like this in many other parts of the file, but I don't think we do that generally in LLVM; I'd prefer Count. Maybe not worth changing now :-/

2697

Use // instead of /*

2698

Actually, Jump doesn't seem like a great name. Maybe we could have WordShift and BitShift?

[craig.topper]

I want to look at left shift at some point. Also making an in place version of ashr as well. lshrInPlace was just added last week which is why I focused on it.

[craig.topper]

Update comments and variable names. Add some basic tests.

[hans]

lgtm2

include/llvm/ADT/APInt.h

     return R;
   }
 
-  /// Logical right-shift this APInt by shiftAmt in place.
-  void lshrInPlace(unsigned shiftAmt);
+  /// Logical right-shift this APInt by ShiftAmt in place.
+  void lshrInPlace(unsigned ShiftAmt);
 
   /// \brief Left-shift function.
   ///

 
   /// Shift a bignum right COUNT bits.  Shifted in bits are zero.  There are no
   /// restrictions on COUNT.
-  static void tcShiftRight(WordType *, unsigned parts, unsigned count);
+  static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
 
   /// The obvious AND, OR and XOR and complement operations.
   static void tcAnd(WordType *, const WordType *, unsigned);

lib/Support/APInt.cpp

   return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth));
 }
 
-/// Perform a logical right-shift from Src to Dst of Words words, by Shift,
-/// which must be less than 64. If the source and destination ranges overlap,
-/// we require that Src >= Dst (put another way, we require that the overall
-/// operation is a right shift on the combined range).
-static void lshrWords(APInt::WordType *Dst, APInt::WordType *Src,
-                      unsigned Words, unsigned Shift) {
-  assert(Shift < APInt::APINT_BITS_PER_WORD);
-
-  if (!Words)
-    return;
-
-  if (Shift == 0) {
-    std::memmove(Dst, Src, Words * APInt::APINT_WORD_SIZE);
-    return;
-  }
-
-  uint64_t Low = Src[0];
-  for (unsigned I = 1; I != Words; ++I) {
-    uint64_t High = Src[I];
-    Dst[I - 1] =
-        (Low >> Shift) | (High << (APInt::APINT_BITS_PER_WORD - Shift));
-    Low = High;
-  }
-  Dst[Words - 1] = Low >> Shift;
-}
-
 /// Logical right-shift this APInt by shiftAmt.
 /// @brief Logical right-shift function.
-void APInt::lshrInPlace(unsigned shiftAmt) {
+void APInt::lshrInPlace(unsigned ShiftAmt) {
   if (isSingleWord()) {
-    if (shiftAmt >= BitWidth)
+    if (ShiftAmt >= BitWidth)
       VAL = 0;
     else
-      VAL >>= shiftAmt;
+      VAL >>= ShiftAmt;
     return;
   }
 
-  // Don't bother performing a no-op shift.
-  if (!shiftAmt)
-    return;
-
-  // Find number of complete words being shifted out and zeroed.
-  const unsigned Words = getNumWords();
-  const unsigned ShiftFullWords =
-      std::min(shiftAmt / APINT_BITS_PER_WORD, Words);
-
-  // Fill in first Words - ShiftFullWords by shifting.
-  lshrWords(pVal, pVal + ShiftFullWords, Words - ShiftFullWords,
-            shiftAmt % APINT_BITS_PER_WORD);
-
-  // The remaining high words are all zero.
-  for (unsigned I = Words - ShiftFullWords; I != Words; ++I)
-    pVal[I] = 0;
+  return tcShiftRight(pVal, getNumWords(), ShiftAmt);
 }
 
 /// Left-shift this APInt by shiftAmt.

 
 /* Shift a bignum right COUNT bits in-place.  Shifted in bits are
    zero.  There are no restrictions on COUNT.  */
-void APInt::tcShiftRight(WordType *dst, unsigned parts, unsigned count) {
-  if (count) {
-    /* Jump is the inter-part jump; shift is is intra-part shift.  */
-    unsigned jump = count / APINT_BITS_PER_WORD;
-    unsigned shift = count % APINT_BITS_PER_WORD;
-
-    /* Perform the shift.  This leaves the most significant COUNT bits
-       of the result at zero.  */
-    for (unsigned i = 0; i < parts; i++) {
-      WordType part;
+void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) {
+  // Don't bother performing a no-op shift.
+  if (!Count)
+    return;
 
-      if (i + jump >= parts) {
-        part = 0;
-      } else {
-        part = dst[i + jump];
-        if (shift) {
-          part >>= shift;
-          if (i + jump + 1 < parts)
-            part |= dst[i + jump + 1] << (APINT_BITS_PER_WORD - shift);
-        }
-      }
+  /* Jump is the inter-part jump; Shift is is intra-part shift.  */
+  unsigned Jump = std::min(Count / APINT_BITS_PER_WORD, Words);
+  unsigned Shift = Count % APINT_BITS_PER_WORD;
 
-      dst[i] = part;
+  unsigned WordsToMove = Words - Jump;
+  // Fastpath for moving by whole words.
+  if (Shift == 0) {
+    std::memmove(Dst, Dst + Jump, WordsToMove * APINT_WORD_SIZE);
+  } else {
+    for (unsigned i = 0; i != WordsToMove; ++i) {
+      Dst[i] = Dst[i + Jump] >> Shift;
+      if (i + 1 != WordsToMove)
+        Dst[i] |= Dst[i + Jump + 1] << (APINT_BITS_PER_WORD - Shift);
     }
   }
+
+  // Fill in the remainder with 0s.
+  std::memset(Dst + WordsToMove, 0, Jump * APINT_WORD_SIZE);
 }
 
 /* Bitwise and of two bignums.  */