Add builtins for aligning and checking alignment of pointers and integers

This change introduces three new builtins (which work on both pointers
and integers) that can be used instead of common bitwise arithmetic:
__builtin_align_up(x, alignment), __builtin_align_down(x, alignment) and
__builtin_is_aligned(x, alignment).

I originally added these builtins to the CHERI fork of LLVM a few years ago
to handle the slightly different C semantics that we use for CHERI [1].
Until recently these builtins (or sequences of other builtins) were
required to generate correct code. I have since made changes to the default
C semantics so that they are no longer strictly necessary (but using them
does generate slightly more efficient code). However, based on our experience
using them in various projects over the past few years, I believe that adding
these builtins to clang would be useful.

These builtins have the following benefit over bit-manipulation and casts
via uintptr_t:

- The named builtins clearly convey the semantics of the operation. While
  checking alignment using __builtin_is_aligned(x, 16) versus
  ((x & 15) == 0) is probably not a huge win in readably, I personally find
  __builtin_align_up(x, N) a lot easier to read than (x+(N-1))&~(N-1).
- They preserve the type of the argument (including const qualifiers). When
  using casts via uintptr_t, it is easy to cast to the wrong type or strip
  qualifiers such as const.
- If the alignment argument is a constant value, clang can check that it is
  a power-of-two and within the range of the type. Since the semantics of
  these builtins is well defined compared to arbitrary bit-manipulation,
  it is possible to add a UBSAN checker that the run-time value is a valid
  power-of-two. I intend to add this as a follow-up to this change.
- The builtins avoids int-to-pointer casts both in C and LLVM IR.
  In the future (i.e. once most optimizations handle it), we could use the new
  llvm.ptrmask intrinsic to avoid the ptrtoint instruction that would normally
  be generated.
- They can be used to round up/down to the next aligned value for both
  integers and pointers without requiring two separate macros.
- In many projects the alignment operations are already wrapped in macros (e.g.
  roundup2 and rounddown2 in FreeBSD), so by replacing the macro implementation
  with a builtin call, we get improved diagnostics for many call-sites while
  only having to change a few lines.
- Finally, the builtins also emit assume_aligned metadata when used on pointers.
  This can improve code generation compared to the uintptr_t casts.

[1] In our CHERI compiler we have compilation mode where all pointers are
implemented as capabilities (essentially unforgeable 128-bit fat pointers).
In our original model, casts from uintptr_t (which is a 128-bit capability)
to an integer value returned the "offset" of the capability (i.e. the
difference between the virtual address and the base of the allocation).
This causes problems for cases such as checking the alignment: for example, the
expression `if ((uintptr_t)ptr & 63) == 0` is generally used to check if the
pointer is aligned to a multiple of 64 bytes. The problem with offsets is that
any pointer to the beginning of an allocation will have an offset of zero, so
this check always succeeds in that case (even if the address is not correctly
aligned). The same issues also exist when aligning up or down. Using the
alignment builtins ensures that the address is used instead of the offset. While
I have since changed the default C semantics to return the address instead of
the offset when casting, this offset compilation mode can still be used by
passing a command-line flag.

Reviewers: rsmith, aaron.ballman, theraven, fhahn, lebedev.ri, nlopes, aqjune
Reviewed By: aaron.ballman, lebedev.ri
Differential Revision: https://reviews.llvm.org/D71499

1 files changed, 73 insertions, 0 deletions

diff --git a/clang/docs/LanguageExtensions.rst b/clang/docs/LanguageExtensions.rst
index b0f57202e07..0bd87903f34 100644
--- a/clang/docs/LanguageExtensions.rst
+++ b/clang/docs/LanguageExtensions.rst
@@ -2509,6 +2509,79 @@ the invocation point is the same as the location of the builtin.
 When the invocation point of ``__builtin_FUNCTION`` is not a function scope the
 empty string is returned.
 
+Alignment builtins
+------------------
+Clang provides builtins to support checking and adjusting alignment of
+pointers and integers.
+These builtins can be used to avoid relying on implementation-defined behavior
+of arithmetic on integers derived from pointers.
+Additionally, these builtins retain type information and, unlike bitwise
+arithmentic, they can perform semantic checking on the alignment value.
+
+**Syntax**:
+
+.. code-block:: c
+
+  Type __builtin_align_up(Type value, size_t alignment);
+  Type __builtin_align_down(Type value, size_t alignment);
+  bool __builtin_is_aligned(Type value, size_t alignment);
+
+
+**Example of use**:
+
+.. code-block:: c++
+
+  char* global_alloc_buffer;
+  void* my_aligned_allocator(size_t alloc_size, size_t alignment) {
+    char* result = __builtin_align_up(global_alloc_buffer, alignment);
+    // result now contains the value of global_alloc_buffer rounded up to the
+    // next multiple of alignment.
+    global_alloc_buffer = result + alloc_size;
+    return result;
+  }
+
+  void* get_start_of_page(void* ptr) {
+    return __builtin_align_down(ptr, PAGE_SIZE);
+  }
+
+  void example(char* buffer) {
+     if (__builtin_is_aligned(buffer, 64)) {
+       do_fast_aligned_copy(buffer);
+     } else {
+       do_unaligned_copy(buffer);
+     }
+  }
+
+  // In addition to pointers, the builtins can also be used on integer types
+  // and are evaluatable inside constant expressions.
+  static_assert(__builtin_align_up(123, 64) == 128, "");
+  static_assert(__builtin_align_down(123u, 64) == 64u, "");
+  static_assert(!__builtin_is_aligned(123, 64), "");
+
+
+**Description**:
+
+The builtins ``__builtin_align_up``, ``__builtin_align_down``, return their
+first argument aligned up/down to the next multiple of the second argument.
+If the value is already sufficiently aligned, it is returned unchanged.
+The builtin ``__builtin_is_aligned`` returns whether the first argument is
+aligned to a multiple of the second argument.
+All of these builtins expect the alignment to be expressed as a number of bytes.
+
+These builtins can be used for all integer types as well as (non-function)
+pointer types. For pointer types, these builtins operate in terms of the integer
+address of the pointer and return a new pointer of the same type (including
+qualifiers such as ``const``) with an adjusted address.
+When aligning pointers up or down, the resulting value must be within the same
+underlying allocation or one past the end (see C17 6.5.6p8, C++ [expr.add]).
+This means that arbitrary integer values stored in pointer-type variables must
+not be passed to these builtins. For those use cases, the builtins can still be
+used, but the operation must be performed on the pointer cast to ``uintptr_t``.
+
+If Clang can determine that the alignment is not a power of two at compile time,
+it will result in a compilation failure. If the alignment argument is not a
+power of two at run time, the behavior of these builtins is undefined.
+
 Non-standard C++11 Attributes
 =============================