Aug 14, 2004

//===---------------------------------------------------------------------------===//
//  LLVM Object Alignment Definitions
//

We need to be able to support non-default alignment on all LLVM memory object 
definitions, as well as on loads and stores.  In particular, we should support
object definitions like this:

%X = global int 4, align 8
%Y = uninitialized global int, align 16
declare void %foo(int) align 8
void %bar(int) align 16 { ... }

...
   %P = alloca int, uint 17, align 32
   %Q = malloc float, uint 1, align 64
...

Alignments are always required to be a power of two, and should be encoded as such,
requiring only a byte in the .bc files.  A value of 0 in the .ll file should be a
parse error.  An object definition with a specified alignment guarantees that the
alignment will be at least a multiple of the specified number.  If the specified
value is less than the natural alignment for the object for a particular target, the
alignment can be removed from the definition without losing anything.  TargetData
should contain a property that indicates the alignment of memory returned by malloc
(it should default to 8) on that target.

Code generation for these things is a little tricky.  For the C backend, we must
use GCC extensions to support these, and codegen malloc as memalign when appropriate.
For native targets, things are simpler, but the stack frame layout code will have to
be taught to insert dynamic stack pointer alignment code if a stack frame contains
objects that have greater alignment than the guaranteed maintained alignment of the
stack frame.

In llvmgcc, we can generate these alignment definitions directly from the GCC
alignment attribute.  Other languages can produce them from other means, for example
a front-end that requires function pointers to be aligned to a certain boundary.

//===---------------------------------------------------------------------------===//
//  LLVM Load/Store Alignment
//

Loads and stores also need to have an alignment specified for them.  For example:

  %V = load int* %P
  %V = load int* %P, align 8      ;; We know it's aligned more
  %V = load int* %P, align 2      ;; We don't know that it's aligned enough!
  store int 4, int* %P, align 1   ;; Analogous to load cases.

Note that alignments both above and below the standard target alignment impart
useful information.  In particular, alignments larger than the default alignment
give analyses and optimizations information, and can be the result of alignment
propagation (an important part of vectorization).

Alignments smaller than the target default indicate that the code generator for the
target needs to generate special code to support the load/store.  In particular,
some architectures have special load/store instructions for unaligned memory
addresses that are less efficient than those for known-aligned addresses (e.g.
Intel SSE).  For targets without unaligned memory access support, the code
generator would need to synthesize the load or store from a combination of
operations.  For example, an unaligned load can be code generated with something
like this:

   %V = load int* %P, align 1

  R1 = and PReg, 3
  R2 = and PReg, ~3
  R3 = load [R2]
  R4 = load [R2+4]
  R5 = shr R3, R1
  R6 = sub 3, R1
  R7 = shl R4, R6
  V  = or R5, R7

There are probably more efficient ways to do this, but the point is that it can be
done.  To support this, the code generator description for the various target
load/store instructions should indicate the required alignment for the various
load/store operations.  This means they should be defined something like this:

  (set $rd, (load $src, 4))    ;; Requires 4 byte alignment
  (set $rd, (load $src, 1))    ;; Requires 1 byte alignment

Obviously it would be nice to allow targets to globally define the default alignment
for loads/stores, so that only exceptional instructions need explicit alignments
specified.