!standard 13.03(23)                                   04-02-05  AC95-00091/01
!class amendment 03-12-12
!status received no action 03-12-12
!status received 03-12-12
!subject Some gripe about Alignment

!summary

!appendix

From: Michael F. Yoder
Sent: Friday, December 12, 2003 12:09 PM

This is as good a place as any to insert my own (minor) "Annex J" gripe.

I've wished for some time that "at mod" clauses would be taken out of
the annex, but not with their current semantics.

The clause "at mod n" is interpreted to mean that the record type has
alignment n.  This is a redundant feature, and deserves to be called
obsolescent.

However, up until Ada 95 was defined, I always thought the "at mod n"
clause specified that the record type had alignment that was a
*multiple* of n, rather than specifying n exactly.  This is a genuinely
useful feature.  It can be emulated by adding a zero-sized dummy field
with alignment n, but this is ugly.  (And, in light of the debate about
zero-sized objects and access values, the field might end up taking up
space after all.)

The case that comes to mind where I last wanted this looked something
like this:

    type R is record at mod 2;
             Data: T; -- a generic private type
     end record;
    type AR is access R;

The point was to insure that the addresses were multiples of 2 so that
the low-order bit of values of type AR could be used in atomic-swap
algorithms as a lock bit.  The "multiple of 2" semantics is needed so
that the type T can have any alignment; the actual alignment of type R
will be the least common multiple of 2 and the alignment of T.

****************************************************************

From: Robert Dewar
Sent: Friday, December 12, 2003  3:30 PM

Sorry, I am confused,

for X'Alignment use 2;

precisely means that objects of X have an alignment that is a multiple
(any multiple) of two bytes.

Perhaps I am missing something here???

****************************************************************

From: Robert A. Duff
Sent: Friday, December 12, 2003  3:56 PM

That was my initial reaction.  But, yes, I think you're missing
something (as I was, initially).

    for X'Alignment use 2;

means two things:

    - If the compiler allocates an object of type X, it must choose an
      address that is a multiple of 2.

    - If the compiler generates code to refer to an object of type X,
      it can assume that X'Address is a multiple of 2, but it cannot
      assume more.

The second point is only interesting for objects whose allocation is not
under control of the compiler.  For example, an object imported from
another language.  When loading an object of type X (or components
thereof) into a register, the compiler must ensure that the code won't
crash when the address is not a multiple of 4, if the object was
allocated by C code or whatever.

Another example is user-defined storage pools.  If the pool returns
address 1_000_006, the generated code has to work.  (Presuming the
compiler didn't reject the Alignment clause, of course, which I suspect
it would do if the target machine can't easily handle that alignment for
that type.)

What Mike Yoder is asking for is a way to say "Please make the alignment
at least 2, but 4 or 8 is OK, too."  It would imply that the compiler
can assume 4, if it likes, and then a user-defined storage pool would
have to use 4, not 2.

****************************************************************

From: Robert A. Duff
Sent: Friday, December 12, 2003  4:10 PM

> Sorry, I am confused,

I tried to alleviate that confusion in my previous message. ;-)

But now I'd like to say:
I'm surprised by Mike's interpretation of Ada 83.  I believe I'm
responsible for writing the Ada 95 alignment rules, and I honestly
thought I was transcribing *exactly* the Ada 83 rules, except that
the syntax changed so it wasn't restricted to record types, but was
allowed for all kinds of types.  I truly believed that "for T'Alignment
use ..." meant exactly the same thing (for record types) as the "at mod"
syntax (which was only allowed for record types).

Does anybody have an opinion as to what the Ada 83 syntax meant?

I (now) agree with Mike that "This is a genuinely useful feature."
I wouldn't restrict it to records, either.  I would call it,
"for T'Min_Alignment use...".

****************************************************************

From: Robert Dewar
Sent: Friday, December 12, 2003  5:36 PM

>     - If the compiler generates code to refer to an object of type X,
>       it can assume that X'Address is a multiple of 2, but it cannot
>       assume more.

OK, I got it. Well my reaction is this is may be a layer of hard to
understand complication to an already complex notion (alignment) that
many users have a lot of difficulties with.

I think it is certainly out of the question to modify the semantics of
the existing syntactic forms (which definitely mean the same thing, and
indeed provide a two-way guarantee).

But let's get into positive mode and make a suggestion.

In GNAT, we have an attribute Object_Size that gives the size to be
allocated for objects of the type (as opposed to the Value_Size which
is the size of the type, used in unchecked allocation and packing).

So, by analogy

    for X'Object_Alignment use bla;

This means that objects of this type that are allocated by the compiler
should get this alignment where possible unless overridden.

Value_Alignment then refers to the guaranteed alignment that the
compiler can assume for all values of the type.

Example:

    type R is array (1 .. 8) of Character;
    for R'Value_Alignment use 1;
    for R'Object_Alignment use 8;

Now the compiler can handle any alignment for values of this type
(e.g. values that come from unchecked conversion of arbitrary
addresses), but if it allocates a value of this type, they are
allocated on an 8-byte boundary.

A normal definition of 'Alignment would set both alignment
values.

By the way is the ARG considering adopting Value_Size and
Object_Size? We find these very useful in the GNAT environment.

****************************************************************

From: Robert Dewar
Sent: Friday, December 12, 2003  5:44 PM

> I'm surprised by Mike's interpretation of Ada 83.

I think there is no authority at all for Mike to consider that
the alignment clause in Ada 83 meant anything different. As one
of the people most involved in understanding and testing the
chapter 13 requirements I can tell you that I have never heard
this interpretation before, and certainly Ada 83 compilers
used the value in the alignment clause to align data.

****************************************************************

From: Michael F. Yoder
Sent: Friday, December 12, 2003  6:21 PM

> I think there is no authority at all for Mike to consider that
> the alignment clause in Ada 83 meant anything different. [snip]

This is amusing, because I derived it from what has come to be called
Dewar's rule, namely that the language doesn't require silly things; it
was my belief (while I was an Ada 83 implementer) that the alternative
interpretation was obviously wrong.  The alignment of a record must (in
most implementations) be a multiple of the LCM of its components'
alignments, and those aren't always known at compile time (if, e.g.,
they are of generic private types).

But let's follow through with this logic.  Suppose I do this:

    generic
          type T is private;
     package G is
           type R is record
               C: T;
           end record;
           for R'Alignment use 2;
     end package G;

If I now instantiate G with an actual type whose alignment is 4, is it
an illegal instantiation?  Or does the type R in the instance become
alignment 4?  Or is there another choice?

****************************************************************

From: Robert Dewar
Sent: Friday, December 12, 2003  6:57 PM

Michael F. Yoder wrote:

>>>>> However, up until Ada 95 was defined, I always thought the "at mod
>>>>> n" clause specified that the record type had alignment that was a
>>>>> *multiple* of n, rather than specifying n exactly.  This is a
>>>>> genuinely useful feature.

The importance of this is that both interpretations are compatible with
the above language. That's why I needed Bob's intervention to understand
your point. Merely saying the above is not sufficient, because of course
when you say

    for X'Alignment use 4;

You precisely mean that the alignment of objects of type X must be
divisible by 4 (it can of course also be divisible by 16 or 4096).

I still an not clear what you expect here.

If you are wondering about a compiler that does the following:

    type X is new Long_Long_Integer;   -- 8 bytes, default alignment 8
    for X'Alignment use 4;

    but the compiler still, allocates all objects of type X on a boundary
    of 8.

Well that of course is 100% compatible with the RM.

I think to make your point clear, you need to write a program which
would be illegal under your interpretation and legal under the
interpretation you think is implied in Ada 95 (since I don't know
how they differ, I don't know what I mean here), or vice versa.

> This is amusing, because I derived it from what has come to be called
> Dewar's rule, namely that the language doesn't require silly things; it
> was my belief (while I was an Ada 83 implementer) that the alternative
> interpretation was obviously wrong.  The alignment of a record must (in
> most implementations) be a multiple of the LCM of its components'
> alignments, and those aren't always known at compile time (if, e.g.,
> they are of generic private types).

No, it is perfectly fine for the compiler to allow the default
alignment to be overridden. Let's consider this

	procedure k is
    	   type r is new integer range 1 .. 10;
	   for r'alignment use 4;

	   type s is record
	      r1 : r;
	   end record;

	   for s'alignment use 2;
	begin
	   null;
	end k;

Now the compiler does not have to accept this (and nothing in the
Ada 83 or Ada 95 RM requires this to be accepted), but on the other
hand, it is perfectly fine for the compiler to accept it.

GNAT takes the view that it will not allow this in the default
case, but if the record s is repped:

	procedure k is
    	   type r is new integer range 1 .. 10;
	   for r'alignment use 4;

	   type s is record
	      r1 : r;
	   end record;

	   for s use record
	     r1 at 0 range 0 .. 31;
	   end record;

	   for s'alignment use 2;
	begin
	   null;
	end k;

Now GNAT will accept this version of the program.
>
> But let's follow through with this logic.  Suppose I do this:
>
>    generic
>          type T is private;
>     package G is
>           type R is record
>               C: T;
>           end record;
>           for R'Alignment use 2;
>     end package G;
>
> If I now instantiate G with an actual type whose alignment is 4, is it
> an illegal instantiation?  Or does the type R in the instance become
> alignment 4?  Or is there another choice?

The compiler may or may not allow this. There is nothing in either the
Ada 83 or Ada 95 RM that either prohibits or requires the compiler
to accept such an instantiation.

So, Mike, the challenge remains. Please show a program which shows
the difference in terms of required behavior. I can't see one and
it seems to me that compilers are free to behave either way, so
making some surgery in the language in the direction you suggest
has precisely zero effect on the set of programs required to be
accepted, and on the set of programs required to be rejected.

Remember that you can never make statements about the choice of
default alignments. It is fine for instance for compilers to
make the default alignment depend on whether the variable name
contains the letter Z. Bizarre, but conforming.

I think what may be happening is that you are thinking something
like: an alignment clause does not change the default alignment
of allocated objects. But such a statement is meaningless since
the default alignment is non-deterministic.

However, take a look at my proposal. This I think captures what
you have in mind???

****************************************************************

From: Michael F. Yoder
Sent: Saturday, December 13, 2003 10:45 AM

>I (now) agree with Mike that "This is a genuinely useful feature."
>I wouldn't restrict it to records, either.  I would call it,
>"for T'Min_Alignment use...".

This idea is superior to what I implicitly suggested.  (Namely, to
resurrect "at mod" clauses with what I thought were the Ada 83
semantics.)  So, I retract my gripe, and am content to see them left in
Annex J.  Instead, I'll briefly plug Bob's suggestion: to the best of my
recollection I've *always* wished I had the "min alignment" semantics
when giving alignments, and I've never wanted to specify alignment exactly.

****************************************************************

From: Robert Dewar
Sent: Saturday, December 13, 2003 11:44 AM

Once again, this is confused, since the current Alignment attribute is
precisely a minimum alignment attribute. Try formalizing this proposal
and I bet it does not work!

****************************************************************

From: Michael F. Yoder
Sent: Sunday, December 14, 2003 11:45 AM

You are confusing alignment of objects with the value of the 'Alignment
attribute, unless you are asserting that if I specify

    for T'Alignment use 4;

it is possible for T'Alignment to become something other than 4.

Yes, T'Alignment specifies the min alignment of objects of type T.  That
isn't what is at issue here.  What is wanted is the ability to say
"T'Alignment must be a multiple of n, but I don't need it to be exactly
n."  This is most useful when T is a composite type with components of
generic formal types whose alignments are unknown at compile time, but
it can also be useful for maintenance reasons.  One might wish
R'Alignment to be the LCM of 2 and whatever alignments its components
happen to have; this is easily done by saying

   for R'Min_Alignment use 2;

and this will remain the right rep spec when highly aligned components
are added or deleted during maintenance.

****************************************************************

From: Robert Dewar
Sent: Sunday, December 14, 2003 12:24 PM

> Yes, T'Alignment specifies the min alignment of objects of type T.  That
> isn't what is at issue here.  What is wanted is the ability to say
> "T'Alignment must be a multiple of n, but I don't need it to be exactly
> n."

But specifying an alignment of n *MEANS* that the address is a multiple
of N. The idea of alignment being *exactly* N is odd. Now I think what
you really mean is that you want the compiler to be able to use a larger
alignment for all its allocations etc. Well that's fine, it is free to
do this if it wants right now.

> This is most useful when T is a composite type with components of
> generic formal types whose alignments are unknown at compile time, but
> it can also be useful for maintenance reasons.  One might wish
> R'Alignment to be the LCM of 2 and whatever alignments its components
> happen to have; this is easily done by saying
>
>   for R'Min_Alignment use 2;
>
> and this will remain the right rep spec when highly aligned components
> are added or deleted during maintenance.

But your Min_Alignment has EXACTLY the same semantics in terms of
programs that are required to be accepted and required to be rejected
as the current Alignment semantics.

Please show a program where you could tell the difference!

The program you showed before was one that might or might not be
accepted by the compiler with either possible semantics, and it is
my contention that there are no programs whose legality depends on
the difference.

A compiler is allowed, but not required, to use higher alignments
for all allocated objects of the type in either case.

****************************************************************

From: Tucker Taft
Sent: Sunday, December 14, 2003  6:02 PM

As Bob explained, the only place where it would matter
is if the object is allocated outside of the control
of the compiler, and it was not aligned any more than
the specified alignment.  E.g., for an imported object,
or an address to access conversion.  The RM says the
compiler may not presume it is more aligned than T'Alignment,
and hence cannot use instructions that presume more
alignment than that on objects that might have been allocated
outside of its control.  For example, if you have a user-defined
storage pool, and the allocation routine is passed the alignment,
then it doesn't have to allocate storage any more aligned than
specified.

A rather kludgey workaround for this is as follows:

   type Underlying is record
       X : Whatever;
       Y : Whoever;
   end record;

   type T is new Underlying;
   for T'Alignment use Integer'Max(Underlying'Alignment, 2);

This will give T the max of the "natural" alignment
of Underlying and 2, which would accomplish your goal if you
can be certain that the natural alignment is always
a power of 2.  If your machine was truly bizarre, then
you would need some kind of static least-common-multiple
function, but I think the number of machines that have
non-power-of-2 alignments can be counted on the fingers
of zero hands.  (Note that I am aware of machines whose
word size is not a multiple of 2, and I am aware of machines
that have 3-word floating point types, but none that have
alignment requirements in storage units that are not
a power of 2.)

****************************************************************

From: Robert Dewar
Sent: Monday, December 15, 2003 12:47 AM

There is nothing to stop the compiler from allocating things
more aligned.

> A rather kludgey workaround for this is as follows:
>
>    type Underlying is record
>        X : Whatever;
>        Y : Whoever;
>    end record;
>
>    type T is new Underlying;
>    for T'Alignment use Integer'Max(Underlying'Alignment, 2);

But there is no requirement that the compiler give any particular
alignment for Underlying, so this does not achieve any guaranteed
effect.

You are trying to talk about the "natural" (or I suppose) default
alignment of things, but the RM has nothing to say about that.

I would like to see this formalized, I think you are getting
confused between formal language semantics and some informal
pragmatic notion of what you expect.

****************************************************************

From: Michael F. Yoder
Sent: Monday, December 15, 2003 10:09 PM

> But specifying an alignment of n *MEANS* that the address is a
> multiple of N. The idea of alignment being *exactly* N is odd. Now I
> think what
> you really mean is that you want the compiler to be able to use a larger
> alignment for all its allocations etc. Well that's fine, it is free to
> do this if it wants right now.

This is simply incorrect.  The idea of alignment being exactly n is odd
for objects, but not for types.  For types, T'Alignment being exactly n
means precisely that T'Alignment = n.  This generally means two things:
first, that objects must be allocated at an address that's a multiple of
n.  Second, that the compiler can't assume a higher alignment than this
when generating code for, e.g., parameters of type T.

What I want isn't that the compiler is *allowed* to use a larger
alignment, I want it to be *required* to use a larger alignment when
needed.  Specifically, I want the least alignment that is a multiple of
my specified minimum alignment *and* the alignment of any component
types.  (Said multiple may be equal to n, but it may not be.)

Here's a contrived example to illustrate the point.  Suppose the storage
unit is 8 bits.

   type TM is mod 2**32;
   for TM'Size use 32;
   for TM'Alignment use 4;

   type R is record
       Modulus: TM;
   end record;
   for R'Size use 32;
   for R'Alignment use 2;

I would expect a compiler to reject the declaration of R as illegal,
since an allocator could create an object of type R that was at an
address congruent to 2 modulo 4, and this would mean its component
Modulus wasn't aligned modulo 4.

If the alignment clause were "for R'Min_Alignment use 2;" the
declaration would be fine, and R'Alignment would become 4.

The problem from a maintenance point of view is that using exact
specification of alignments (rather than the min alignment semantics)
requires that the programmer who writes the alignment clause for R be
aware of the alignments of all component types, and to do a LCM.  Here,
since TM is a static type, it's possible to write

   for R'Alignment use Integer'Max (2, TM'Alignment);

But this isn't always available.  And if TM were a generic formal type
there would be no way to express what's wanted.

****************************************************************

From: Robert A. Duff
Sent: Monday, December 15, 2003 12:09 PM

> There is nothing to stop the compiler from allocating things
> more aligned.

But the issue is when the compiler is not allocating -- user-written
code is, or a foreign language.

Let me add some chapter-and-verse to Mike Yoder's example:

>    type TM is mod 2**32;
>    for TM'Size use 32;
>    for TM'Alignment use 4;
>
>    type R is record
>        Modulus: TM;
>    end record;
>    for R'Size use 32;
>    for R'Alignment use 2;

    type A is access all R;
    for A'Storage_Pool use My_Pool;

    procedure P(X: in out A) is
    begin
        X.all.Modulus := X.all.Modulus + 1; -- (*)
    end P;

    P(new R'(Modulus => 123));
      -- Calls Allocate(My_Pool, Alignment => 2, ...)

RM-13.1(17) requires that R'Alignment = 2.  The compiler is not allowed
to return 4.

13.11(16) requires the compiler to pass 2 as the Alignment parameter to
the Allocate procedure.  The compiler is not allowed to pass 4.

The (user-written) Allocate procedure may then return an address that is
divisible by 2 but not by 4.  The code at (*) is then *required* to work
when X.Modulus'Address is not divisible by 4; it cannot use load/store
instructions that will fail in that case.

The compiler could instead make "for R'Alignment use 2;" illegal.
But it cannot accept this representation clause, and then pass
Alignment => 4 to Allocate.

The same issue arises with imported objects:

    Imp: aliased R;
    pragma Import(C, Imp);

    P(Imp'Access);

If the C compiler allocates Imp at an address not divisible by 4,
then the code at (*) is required to work (unless the Ada compiler
rejects the "for R'Alignment use 2;").

****************************************************************

From: Robert Dewar
Sent: Tuesday, December 16, 2003  9:55 AM

OK, so the issue really revolves around the argument
given to the storage pool. In fact what I would like
to see here is that the alignment for objects can be
greater than the alignment for types. This has a
perfect analogy for sizes.

The alignment for a type gives the guarantee that all
objects of the type have at least this alignment, just
as the size for a type gives the guarantee that all
objects of this type have at least this size.

Just as we expect the compiler to give larger sizes
for objects for the sake of efficiency, we can expect
a compiler to give larger alignments to objects for
efficiency purposes.

Now in Ada 95, there is no control over object sizes
(though in GNAT we have added 'Object_Size), and so
currently there would be no control over object
alignments. A feature can certainly be added.

A note here is that I had not particularly concentrated
on storage pools since we have not seen that feature
used at all (except for our special debug storage pool).
I would be interested in hearing of real applications
using this feature. One problem that stands in the way
of general use is that there is no convenient way to
specify a default storage_pool usage, and it is not
easy to come up with one.

One thing that is an important principle to me is that
if a user does not specify an alignment for a type, then
they have no right to assume anything about alignment of
objects of the type.

So why do users specify alignments at all? That's a
question that is useful to answer in understanding the
best approach here.

Most often it is to ensure some compatibility between
different data in some kind of unchecked conversion
situation. Here most certainly the issue is minimum
guarantees.

Sometimes it is for time efficiency purposes, but that's
almost always unreasonable, since to me, the compiler
should be doing that choice, and should know FAR more
than the user can about alignment requirements of the
target machine.

Sometimes it is for space efficiency purposes, where
we dealign things to allow more packing. That's a more
murky area, and one where indeed the issue is about
allocated object alignment.

****************************************************************

From: Robert A. Duff
Sent: Tuesday, December 16, 2003  1:42 PM

Robert wrote:

> A note here is that I had not particularly concentrated
> on storage pools since we have not seen that feature
> used at all (except for our special debug storage pool).
> I would be interested in hearing of real applications
> using this feature.

We use storage pools heavily in our current project at SofCheck.

I know you think ARG members aren't "real" Ada programmers.  ;-)
But this is a real Ada program, depite having been written in
part by ARG members.

We have a coding convention: every access type must have either a
Storage_Pool clause, or "for T'Storage_Size use 0;".  Or a comment
explaining why the coding convention is not followed.

The reason for this convention is that the program is a long-running
server sort of thing, where storage leaks and other memory management
issues are very important, so we want to have explicit control of
storage management, visible in the source code.

I've seen embedded systems where the goal was to segregate different
types of data into different pools.  E.g., have enough space for up
to 100 radar-tracked planes, and up to 500 gizmos, and up to 200 mumbles.
It would be more memory-efficient (on average) to put all those things
in the global heap, but it makes analysis much harder.  If the
requirements say we have to be able to deal with 500 gizmos,
no matter what, then we don't want 3000 mumbles using up the memory
reserved for gizmos.

>... One problem that stands in the way
> of general use is that there is no convenient way to
> specify a default storage_pool usage, and it is not
> easy to come up with one.

I'm not sure what you mean.  Do you mean a way for the user to say "all
access types should use My_Pool, unless otherwise specified"?
Given the convention mentioned above, I would like a way to say
that the default is "for T'Storage_Size use 0;", so I can get
a warning when an allocator exists for an access type that wasn't
intended for allocation.  If you use class-wide types, that happens a
lot.

Another problem with the feature is that there's no way to specify the
pool dynamically, at the site of the allocator -- it has to be
determined at the access type.  We have some kludgery to get around that
limitation.

> So why do users specify alignments at all?

I don't know.

There are exactly two Alignment clauses in our project.  They are both
inside one of our Storage_Pool packages.  The package allocates hunks of
memory, and Allocate allocates small objects within those.  It wants the
hunks aligned to the maximum possible alignment, so that Allocate can
easily and efficiently produce an aligned address.

In a couple of cases, I wanted very large alignments, but I was unable
to use Alignment clauses, because the compilers being used didn't
support alignments above 4 or 8 or something.  Example: page-align
data structures, so I can use operating system services (on Unix and
Windows) to make them read-only and whatnot.  I ended up going outside
the language to get the alignments I wanted.

I think Mike Yoder wanted to specify "Alignment use 2" because he wanted
to steal the low-order bit of addresses for some sort of flag.

****************************************************************