[Align] Add isAligned taking an APInt

[gchatelet]

Summary

This showed up in https://reviews.llvm.org/D153308

[gchatelet]

• Rename variable

[nikic]

This does not look worth an APInt.h include in Alignment.h.

[gchatelet]

@nikic I agree this is not ideal. Whether it is APInt.h including Alignment.h or the opposite...
Do you have a suggestion on where this should land? If at all?

An alternative would be to document how to handle APInt in Alignment.h but not include the code (it wouldn't be tested though).

[jdoerfert]

Make it a template in the header ;)

template<typename APIntTy>
bool isAligned(Align LHS, const APIntTy &SizeInBytes) {
...
}

[arsenm]

Could also add isAligned to APInt?

[gchatelet]

In D153356#4435661, @jdoerfert wrote:

Make it a template in the header ;)

template<typename APIntTy>
bool isAligned(Align LHS, const APIntTy &SizeInBytes) {
...
}

Yep courbet@ made the same suggestion to me but then it conflicts with various types that have implicit conversion to uin64_t most notably TypeSize.
It could work with some enable_it_t incantation but I'm not sure it bears its own weight.

[gchatelet]

In D153356#4439433, @arsenm wrote:

Could also add isAligned to APInt?

I believe @nikic is opposed to this as well as it would also add a dependency.

[arsenm]

In D153356#4440752, @gchatelet wrote:

In D153356#4439433, @arsenm wrote:

Could also add isAligned to APInt?

I believe @nikic is opposed to this as well as it would also add a dependency.

There's no dependency if you just use the raw value instead of the Align wrapper. Also could forward declare Align?

[gchatelet]

In D153356#4440761, @arsenm wrote:

In D153356#4440752, @gchatelet wrote:

In D153356#4439433, @arsenm wrote:

Could also add isAligned to APInt?

I believe @nikic is opposed to this as well as it would also add a dependency.

There's no dependency if you just use the raw value instead of the Align wrapper. Also could forward declare Align?

I just checked and it seems that clang is able to optimize out the additional operations
https://godbolt.org/z/G65eKTY3b

Now it's a bit of a bummer to lose the type since you also lose the isPowerOfTwo semantic associated with it :-/
That was the original motivation behind Align.

Forward declaring wouldn't work as-is because Log2 takes Align by value.
I can try to make it take a const ref instead... let's see.

[gchatelet]

• Implement isAligned as an APInt member function with Align being forward declared.

[arsenm]

llvm/include/llvm/ADT/APInt.h

439

Pass by value or just use the unsigned?

[gchatelet]

llvm/include/llvm/ADT/APInt.h

439

If we pass by value then we can't forward declare anymore as layout information is needed to copy the value.
Using uint64_t means giving up on types and writing .value() at all call sites.

[nikic]

Does isAligned() need to be defined in the header? If it's in the source file then we just need the forward declaration.

[gchatelet]

• Implement the function in the source file to allow pass by value.

[gchatelet]

In D153356#4444104, @nikic wrote:

Does isAligned() need to be defined in the header? If it's in the source file then we just need the forward declaration.

I never thought it would work to forward declare and pass by value even if the implementation is in the source file. Thx for the suggestion!

[nikic]

llvm/lib/Support/APInt.cpp

168

Copy and paste mistake :) You can just drop the comment as it's already in the header.

llvm/unittests/ADT/APIntTest.cpp

1861

What does the k here mean?

[gchatelet]

• Remove comment
• Rename variable

[gchatelet]

llvm/lib/Support/APInt.cpp

168

Duh! Thx : )

llvm/unittests/ADT/APIntTest.cpp

1861

k is for constants but it's not constant here and it's from another style guide... Thx for noticing.

[nikic]

LGTM

llvm/include/llvm/ADT/APInt.h

 #include <optional>
 #include <utility>
 
 namespace llvm {
 class FoldingSetNodeID;
 class StringRef;
 class hash_code;
 class raw_ostream;
+struct Align;
 
 template <typename T> class SmallVectorImpl;
 template <typename T> class ArrayRef;
 template <typename T, typename Enable> struct DenseMapInfo;
 
 class APInt;
 
 inline APInt operator-(APInt);
bool isNegatedPowerOf2() const {
     if (isNonNegative())
       return false;
     // NegatedPowerOf2 - shifted mask in the top bits.
     unsigned LO = countl_one();
     unsigned TZ = countr_zero();
     return (LO + TZ) == BitWidth;
   }
 
+  /// Checks if this APInt -interpreted as an address- is aligned to the
+  /// provided value.
+  bool isAligned(Align A) const;
+
   /// Check if the APInt's value is returned by getSignMask.
   ///
   /// \returns true if this is the value returned by getSignMask.
   bool isSignMask() const { return isMinSignedValue(); }
 
   /// Convert APInt to a boolean value.
   ///
   /// This converts the APInt to a boolean value as a test against zero.
#endif
   /// Computes the number of leading bits of this APInt that are equal to its
   /// sign bit.
   unsigned getNumSignBits() const {
     return isNegative() ? countl_one() : countl_zero();
   }
 
   /// Count the number of trailing zero bits.
   ///
-  /// This function is an APInt version of std::countr_zero. It counts the number
-  /// of zeros from the least significant bit to the first set bit.
+  /// This function is an APInt version of std::countr_zero. It counts the
+  /// number of zeros from the least significant bit to the first set bit.
   ///
   /// \returns BitWidth if the value is zero, otherwise returns the number of
   /// zeros from the least significant bit to the first one bit.
   unsigned countr_zero() const {
     if (isSingleWord()) {
       unsigned TrailingZeros = llvm::countr_zero(U.VAL);
       return (TrailingZeros > BitWidth ? BitWidth : TrailingZeros);
     }

llvm/lib/Support/APInt.cpp

 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/bit.h"
 #include "llvm/Config/llvm-config.h"
+#include "llvm/Support/Alignment.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cmath>
 #include <optional>
 
 using namespace llvm;
if (isSingleWord()) {
     return;
   }
 
   unsigned NumWords = getNumWords();
   for (unsigned i = 0; i < NumWords; ++i)
     ID.AddInteger(U.pVal[i]);
 }
 
+bool APInt::isAligned(Align A) const {
+  if (isZero())
+    return true;
+  const unsigned TrailingZeroes = countr_zero();
+  const unsigned MinimumTrailingZeroes = Log2(A);
+  return TrailingZeroes >= MinimumTrailingZeroes;
+}
+
 /// Prefix increment operator. Increments the APInt by one.
 APInt& APInt::operator++() {
   if (isSingleWord())
     ++U.VAL;
   else
     tcIncrement(U.pVal, getNumWords());
   return clearUnusedBits();
 }

llvm/unittests/ADT/APIntTest.cpp

 //===- llvm/unittest/ADT/APInt.cpp - APInt unit tests ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Support/Alignment.h"
 #include "gtest/gtest.h"
 #include <array>
 #include <optional>
 
 using namespace llvm;
 
 namespace {
 
for (int I = 1; I < N - 1; ++I) {
       EXPECT_TRUE((-MaskVal).isNegatedPowerOf2());
 
       APInt ShiftMaskVal = One.getHighBitsSet(N, I);
       EXPECT_TRUE(ShiftMaskVal.isNegatedPowerOf2());
     }
   }
 }
 
+TEST(APIntTest, isAligned) {
+  struct {
+    uint64_t alignment;
+    uint64_t offset;
+    bool isAligned;
+  } Tests[] = {
+      {1, 0, true},  {1, 1, true},  {1, 5, true},  {2, 0, true},
+      {2, 1, false}, {2, 2, true},  {2, 7, false}, {2, 16, true},
+      {4, 0, true},  {4, 1, false}, {4, 4, true},  {4, 6, false},
+  };
+  for (const auto &T : Tests)
+    EXPECT_EQ(APInt(32, T.offset).isAligned(Align(T.alignment)), T.isAligned);
+  // Tests for APInt that can't represent the alignment.
+  // Here APInt(4, I) can represent values from 0 to 15.
+  EXPECT_TRUE(APInt(4, 0).isAligned(Align(32))); // zero is always aligned.
+  for (int I = 1; I < 16; ++I)
+    EXPECT_FALSE(APInt(4, I).isAligned(Align(32)));
+}
+
 // Test that self-move works with EXPENSIVE_CHECKS. It calls std::shuffle which
 // does self-move on some platforms.
 #ifdef EXPENSIVE_CHECKS
 #if defined(__clang__)
 // Disable the pragma warning from versions of Clang without -Wself-move
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wunknown-pragmas"
 // Disable the warning that triggers on exactly what is being tested.