[cfe-dev] [llvm-dev] RFC: Enforcing pointer type alignment in Clang

[Pete Cooper via cfe-dev]

Hi John

Thanks for the very detailed explanation.  I’m not a language expert, but i felt like i could understand what you want to do here.

In particular, as a user, I’m surprised it doesn’t already work (in the standard) they way you said it should.  That is

 It is not undefined behavior to create a pointer that is less aligned
 than its pointee type.  Instead, it is only undefined behavior to
 access memory through a pointer that is less aligned than its pointee
 type.

I thought the above was how it should work now.  Its the behaviour i expect when I write code already, and as a user i’d hope that this continues to be what we implement.

So yeah, +1 from me.

Thanks,
Pete
> On Jan 14, 2016, at 12:56 PM, John McCall via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> C 6.3.2.3p7 (N1548) says:
>  A pointer to an object type may be converted to a pointer to a
>  different object type. If the resulting pointer is not correctly
>  aligned) for the referenced type, the behavior is undefined.
> 
> C++ [expr.reinterpret.cast]p7 (N4527) defines pointer conversions in terms
> of conversions from void*:
>  An object pointer can be explicitly converted to an object pointer
>  of a different type. When a prvalue v of object pointer type is
>  converted to the object pointer type “pointer to cv T”, the result
>  is static_cast<cv T*>(static_cast<cv void*>(v)).
> 
> C++ [expr.static.cast]p13 says of conversions from void*:
>  A prvalue of type “pointer to cv1 void” can be converted to a
>  prvalue of type “pointer to cv2 T” .... If the original pointer value
>  represents the address A of a byte in memory and A satisfies the alignment
>  requirement of T, then the resulting pointer value represents the same
>  address as the original pointer value, that is, A. The result of any
>  other such pointer conversion is unspecified.
> 
> The clear intent of these rules is that the implementation may assume
> that any pointer is adequately aligned for its pointee type, because any
> attempt to actually create such a pointer has undefined behavior.  It is
> very likely that, if we found a hole in those rules that seemed to permit
> the creation of unaligned pointers, we could go to the committees and
> have that hole closed.  The language policy here is clear.
> 
> There are architectures where this policy is mandatory.  The classic
> example is (I believe) the Cray C90, which provides word-addressed 32-bit
> pointers.  Pointers to most types can use this native representation directly.
> char*, however, requires sub-word addressing, which means void* and char*
> are actually 64 bits in order to permit the storage of the sub-word offset.
> An int* therefore literally cannot express an arbitrary void*.
> 
> Less dramatically, there are architectural features that clearly depend
> on alignment.  It's unreasonable to expect processors to support atomic
> accesses that straddle the basic unit of their cache coherence implementations.
> Supporting small unaligned accesses has a fairly marginal cost in extra
> hardware, but as accesses grow to 128 bits or larger, those costs can spiral
> out of control.  These restrictions are fairly widely understood by compiler
> users.
> 
> Everything below is mushier.  It's clearly advantageous for the compiler to
> be able to make stronger assumptions about alignment when accessing memory.
> ISAs often allow more efficient accesses to properly-aligned memory; for
> example, 32-bit ARM can perform a 64-bit memory access in a single
> instruction, but the address is required to be 8-byte-aligned.  Alignment
> also affects compiler decisions even when the architecture doesn't enforce
> it; for example, it can be profitable to combine two adjacent loads into
> a single, wider load, but this will often slow down code if the wider load is
> no longer properly aligned.
> 
> As is the case with most forms of undefined behavior, programmers have at
> best an abstract appreciation for the positive effects of these optimizations,
> but they have a very concrete understanding of the disruptive life effects
> of being forced to fix crashes from mis-alignment.
> 
> Our standard response in LLVM/Clang is to explain the undefined behavior
> rule, explain the benefits it provides, and politely ask users to, well,
> deal with it.  And that's appropriate; most forms of undefined behavior
> under the standard(s) are reasonable requests with reasonable code
> workarounds.  However, we have also occasionally looked at a particular
> undefined behavior rule and decided that there's a real usability problem
> with enforcing it as written.  In these cases, we use our power as
> implementors to make some subset of that behavior well-defined in order to
> fix that problem.  For example, we did this for TBAA, because we recognized
> that certain "obvious" aliasing violations were idiomatic and only had
> awkward workarounds under the standard.
> 
> There's a similar problem here.  Much like TBAA, fixing it doesn't require
> completely abandoning the idea of enforcing type-based alignment assumptions.
> It does, however, require a significant adjustment to the language rule.
> 
> The problem is this: the standards make it undefined behavior to even
> create an unaligned pointer.  Therefore, as soon as I've got such a
> pointer, I'm basically doomed; it is no longer possible to locally
> work around the problem.  I have to change the type of the pointer to
> something that requires less alignment, and not just where I'm using
> it, or even just within my function, but all the way up to wherever it
> came from.
> 
> For example, suppose I've got this function:
> 
>  void processBuffer(const int32_t *buffer, size_t length) {
>    ...
>  }
> 
> I get a bug report saying that my function is crashing, and I decide
> that the right fix is to make the function handle unaligned buffers
> correctly.  Maybe that's a binary-compatibility requirement, or maybe the
> buffer is usually coming from a serialized format that doesn't guarantee
> alignment, and it's clearly unreasonable to copy the buffer just to satisfy
> my function.
> 
> So how can I make this function handle unaligned buffers?  The type of the
> argument itself means that being passed an unaligned buffer has undefined
> behavior.  Now, I can change that parameter to use an unaligned typedef:
> 
>  typedef int32_t unaligned_int32_t __attribute__((aligned(1)));
>  void processBuffer(const unaligned_int32_t *buffer, size_t length) {
>    ...
>  }
> 
> But this has severe problems.  First off, this is a GCC/Clang extension; a lot
> of programmers feel uncomfortable adopting that, especially to fix a problem
> that's in principle common across compilers.  Second, alignment attributes
> are not really part of the type system, which means that they can be
> silently dropped by any number of things, including both major features
> like templates and just day-to-day quality-of-implementation stuff like the
> common-type logic of the conditional operator.  And finally, my callers
> still have undefined behavior, and I really need to go audit all of them
> to make sure they're using the same sort of typedef.  This is not a reliable
> solution to the bug.
> 
> Furthermore, the compiler doesn't really care whether the pointer is
> abstractly aligned independent of any access to memory.  There aren't very
> many interesting alignment-based optimizations on pointer values as mere
> values.  In principle, we could optimize operations that cast the pointer
> to an integral type and examine the low bits, but those operations are not
> very common, and when they're there, it's probably for a good reason;
> that's the kind of optimization is very likely to just create miscompiles
> without really showing any benefit.
> 
> Therefore, I would like to propose that Clang formally adopt a significantly
> weaker language rule for enforcing the alignment of pointers.  The basic
> idea is this:
> 
>  It is not undefined behavior to create a pointer that is less aligned
>  than its pointee type.  Instead, it is only undefined behavior to
>  access memory through a pointer that is less aligned than its pointee
>  type.
> 
> That is, the only thing that matters is the type when you actually perform
> the access, not any type the pointer might have had at some earlier point
> during execution.
> 
> Notably, I believe that this rule doesn't require any changes in our
> current behavior, so adopting it is just a restriction on future compiler
> optimization.  For the most part, LLVM IR only attaches alignment to loads,
> stores, and specific intrinsics like llvm.memcpy; there is no way to say
> that a pointer value is expected to have a particular alignment.  The
> one exception that I'm aware of is that an indirect parameter can have
> an expected alignment.  However, Clang currently only sets this for
> by-value arguments that the calling convention says to pass indirectly,
> and that remains acceptable under this new rule because it's an ABI rule
> rather than a constraint on programmer behavior (other than assembly
> programmers).  The rule just means that we can't start setting it on
> arbitrary pointer parameters.
> 
> It is also a very portable rule; I'm not aware of any compilers that do
> try to take advantage of the formal alignment of pointer values independent
> of access.
> 
> The key question in this new rule is what counts as an "access".  I'll spell
> this out in more detail, but it's mostly intuitive: anything that ultimately
> requires a load or store.  The only thing that's perhaps questionable is that
> we'd like to treat calls to library functions that access memory as if they
> were direct accesses to their arguments.  For example, we'd like to assume
> that the pointer arguments to memcpy are properly aligned for their types
> (that is, their explicit types, before the implicit conversion to void*) so
> that we can generate a more efficient copy operation.  This analysis
> currently relies on the language rule that pointers may not be misaligned;
> preserving it requires us to treat calls to library functions as special,
> which of course we already do.  Programmers can still suppress this
> assumption by explicitly casting the arguments to void*.
> 
> Here's the proposed new rule, expressed more formally:
> 
> ---
> 
> It is well-defined behavior to construct a pointer to memory that
> is less aligned than the alignment of the pointee type (if a complete
> type).  However, it is undefined behavior to “access” an expression that
> is an r-value of type T* or an l-value of type T if T is a complete type
> and the memory is less aligned than T.
> 
> An r-value expression of pointer type is accessed if:
> - it is dereferenced (with *) and the resulting l-value is accessed,
> - it is implicitly converted to another pointer type and the
>   result is accessed,
> - it undergoes pointer addition and the result is accessed,
> - it is passed to a function in the C standard library that is known
>   to access the memory,
> - in C++, it is converted to a pointer to a virtual base, or
> - in C++, it is explicitly cast (other than by a reinterpret_cast) to
>   a related class pointer type and the result is accessed.
> 
> An l-value expression is accessed if:
> - it undergoes an lvalue-to-rvalue conversion (i.e. it is loaded),
> - it is the LHS of an assignment operator (including the
>   compound assignments),
> - it is the base of a member access (with .) and the resulting l-value
>   is accessed (recall that x->y is defined as ((*x).y),
> - it undergoes indirection (with &) and the resulting pointer is accessed,
> - in C++, it is implicitly converted to be an l-value to a base type
>   and the result is accessed,
> - in C++, it is converted to be an l-value of a virtual base type,
> - in C++, it is used as the "this""" argument of a call to a
>   non-static member function, or
> - in C++, a reference is bound to it (which includes explicit
>   casts to reference type).
> 
> These are the cases covered by the language standard.  There is a
> very long tail of other kinds of expression that obviously access memory,
> like the atomic and overflow builtins, which I can't reasonably enumerate.
> The intent should be obvious, but I'm willing to spell it out in other
> cases where necessary.
> 
> Note that this definition is *syntactic*, meaning that it is expressed
> in terms of the components of a single statement.  This means that an
> access that might be undefined behavior if written as a single statement:
>  highlyAlignedStruct->charMember = 0;
> may not be undefined behavior if split across two statements:
>  “char *member = &highlyAlignedStruct->charMember;
>  *member = 0;
> In effect, the compiler promises to never propagate alignment assumptions
> between statements through its knowledge of how a pointer was constructed.
> This is necessary in order to allow local workarounds to be reliable.
> 
> Note also that this definition does not propagate through explicit casts,
> other than class-hierarchy casts in C++.  Again, this is a deliberate
> choice to make misalignment workarounds more straightforward.
> 
> But note that this rule does still allow the compiler to make stronger
> abstract assumptions about the alignment of C++ references and the
> "this" pointer.
> 
> ---
> 
> Please let me know what you think.
> 
> John.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev