Version 1.2 of ais/ai-00147.txt

Unformatted version of ais/ai-00147.txt version 1.2
Other versions for file ais/ai-00147.txt

!standard 07.06 (21)          98-09-29 AI95-00147/04
!class binding interpretation 96-06-06
!status work item 98-04-01
!status ARG Approved (with changes) 10-1-2 95-11-01
!status work item 5-1-4 96-10-07
!status work item 96-06-06
!status received 96-06-06
!priority High
!difficulty Hard
!subject Optimization of Controlled Types
!summary 98-09-29
7.6(18-21) does not apply to limited controlled types. Thus, the Initialize and Finalize calls will happen as described in other paragraphs of the Standard.
For non-limited controlled types, the implementation permission of RM-7.6(18-21) is extended as follows:
An implementation is permitted to omit implicit Adjust and Finalize calls and associated assignment operations on an object of non-limited controlled types if
a) any change to the value of the object performed by these calls or
assignment operations do not affect the external effect of any program execution, and
b) any execution of the program that executes an Initialize or Adjust
call on an object will also later execute a Finalize call on the object and will always do so prior to assigning a new value to the object.
This permission applies even if the implicit calls produce side-effects on other objects.
The last sentence of 7.6(21) is amended to include the omission of the finalization of the anonymous object (along with the adjustment) and to exclude the optimization when there are any access values designating the anonymous object as a whole.
!question 98-03-21
RM-7.6(18-21) give implementations permission to eliminate certain calls to Adjust and Finalize. The purpose of these rules is to allow greater efficiency than is implied by the canonical semantics of controlled types. However, it appears that these rules may not go far enough.
Consider first a very simple example:
X: Controlled_Type; -- Initialize(X) begin null; end; -- Finalize(X)
Are the calls really needed for an obviously "dead" variable ? [Yes] Would the Finalize call be eliminatable, if X were explicitly initialized ? [Yes]
Second example:
X: Controlled_Type; -- Initialize(X) begin X := something; -- Finalize(X); Adjust(X); X := something_else; -- Finalize(X); Adjust(X); ... X.Comp -- so that it isn't dead end; -- Finalize(X);
The comments indicate the implicit calls, already taking advantage of the Implementation Permission to omit creation, adjustment and finalization of a temporary anonymous object. Is it really necessary to mandate the execution of the first assignment and its implicit calls, merely for the sake of potential side-effects of these calls ? [No] Do we really have to Initialize and immediately thereafter Finalize X ? [Yes]
Third example:
X1: Controlled_Type; -- Initialize(X1); ... -- no use of X1 declare X: Controlled_Type := Init; -- Adjust(X); begin X1 := X; -- Finalize(X1); Adjust(X1); end; -- Finalize(X); ...
Should the declare block not be optimizable to
X1 := Init; -- Finalize(X1); Adjust(X1) [Yes]
or the whole example to
X1: Controlled_Type := Init; -- Adjust(X1); [No]
avoiding so many unneeded calls ?
Finally, a more complicated example:
function F return Some_Controlled_Type is Result: Some_Controlled_Type := (...); -- Adjust begin return Result; -- Adjust, Finalize end F;
function G return Some_Controlled_Type is Result: Some_Controlled_Type := F; -- Adjust begin return Result; -- Adjust, Finalize end G;
X: Some_Controlled_Type := G; -- Adjust
Is an implementation allowed to optimize the above by creating the aggregate directly in X, thus avoiding all calls to Adjust and Finalize? [Yes] (Such an optimization might well be feasible if F and G are inlined, or if the compiler is doing other kinds of inter-procedural analysis. It might even be feasible without inter-procedural analysis, if the sizes of the function results are known at the call site and there is no danger of source/target overlap.)
Note: Some of these issues came up during a discussion of ACVC test C760007.
Finally, what is the meaning of the last sentence of 7.6(21) ? It seems to allow elimination of an Adjust operation without eliminating a matching Finalize operation. Is this intended ? [No]
!recommendation 98-09-29
For limited controlled types, the canonical semantics apply.
For non-limited controlled types, matching pairs of Adjust/Finalize may be eliminated by the implementation as follows:
For an explicit initialization of an object or an assignment to it, where the assigned value is not read after the Adjust call and prior to the Finalize call for the next assignment to the object or for its destruction, the Adjust/Finalize pair of calls (and the value assignment) need not be performed.
An intermediate recipient object in the flow of a value from a source to its final destination, where the value of the intermediate object is not used thereafter, can be eliminated along with all operations on it by assigning the value directly from its source to the final destination and adjusting it.
The last sentence of 7.6(21) omits an important additional constraint: In order for the adjustment to be omitted, it must also be guaranteed that there are no access values designating the anonymous object as a whole.
!wording 98-09-29
7.6(18-21) need to be carefully rephrased to encompass the permissions stated in the !summary.
The last sentence of 7.6(21) needs to be amended as stated in the
!summary.
!discussion 98-09-29
The above examples show that the implicit calls can create a non-trivial overhead on the execution even when the existing Implementation Permission of RM-7.6. is applied. It is therefore worthwhile to consider extending the Implementation Permission even further.
It is interesting to note that the declare block of the third example above is nothing but an Ada encoding of the canonical semantics of assignments as stated in RM 7.6(17), with the anonymous temporary object being introduced as a named "temporary" object. In the case of the anonymous object, RM 7.6(21) allows the simplification asked for in the question. It seems strange that the explicit introduction of the object in the code should make a significant difference in semantics.
A slight rewriting of the last example would apparently fall under the Implementation Permission, since the "result object" assigned to by the return_statement is an anonymous object:
function F return Some_Controlled_Type is begin return (<<<aggregate>>); end F;
function G return Some_Controlled_Type is begin return F; end G;
X: Some_Controlled_Type := G; -- Adjust
Again, it seems strange that this rewritten version should have semantics different from the original.
So, one question is whether "adjacent" Initialize/Finalize calls or Adjust/Finalize calls without intervening usage of the affected object can be eliminated. The other question is whether the "copy propagation" rule manifest in 7.6(21) for temporary anonymous objects can be extended to "temporary" named objects.
7.6(18-21) does not allow the elimination of Initialize/Finalize pairs -- just Adjust/Finalize pairs, and then only on anonymous objects.
For limited types, this is exactly what we want. Limited controlled types are used, for example, to ensure properly matched calls, such as Lock/Unlock or Open/Close. Another example is a limited controlled type that is used purely because Initialize is an abort-deferred region. That is, a limited controlled object might be used purely for the side-effects of its Initialize and Finalize operations. (It is better to use Initialize for this purpose, rather than Finalize, because then the implementation has a better chance of optimizing away any finalization-related overhead.) Therefore, 7.6(18-21) should certainly not be extended to apply to limited types in any way -- the Initialize and Finalize calls required by the canonical semantics should happen exactly (unless of course the compiler can prove that their side effects are irrelevant). For limited control types, we have exactly one Initialize and exactly one Finalize call, making it possible to exploit the "once-only" semantics in the implementation of these operations.
However, for non-limited types, the situation is somewhat different, since assignments cause additional Adjust and Finalize calls on an object; moreover, many Adjust calls may be applied to a value as it flows from object to object. By virtue of the existing implementation permission, the number of such calls is indeterminate. It is highly advisable that users essentially make Finalize an inverse dual to both Initialize and Adjust, and allow for the possibility of an unknown number of Adjust and Finalize calls on the same object. Consequently, to preserve a canonical semantics that mandates the execution of assignments, even if their only external effect is through the implicit calls on the routines in question, makes little sense, given the already unknown number of call pairs involved.
Conversely, it does make sense to weaken the canonical semantics for the benefit of important optimizations. We can do so by extending the permissions of 7.6(18-21) to Adjust/Finalize pairs for non-limited types in such a way that the practical effect is merely more uncertainty over an already uncertain number of call pairs.
Note also that it is the assignment operation that is abort deferred, not the assignment_statement. Thus, it is possible under canonical semantics for "A := B;" to be aborted after adjusting B in an anonymous temporary object or after finalizing A, but before assigning the new value into A and adjusting it. (Only the latter part is abort deferred.) So, some indeterminacy in the number of Adjust calls is already part of the canonical semantics and not merely a result of existing implementation permissions.
All this argues to give optimizations more leeway in eliminating these implicit calls in situations where "properly written" Adjust and Finalize procedures (i.e., there is no reliance on side-effects other than changes to the value of the object itself) would have no discernable effects on the external effect of the program execution.
In any case, we want to preserve the duality of the calls and guarantee that any program execution that executes an Initialize or Adjust call on an object also executes a Finalize on the object.
Eliminating Initialize/Finalize pairs might seem interesting, but the guaranteed "once-only" semantics of Initialize calls distinguishes them from Adjust calls. Initialize calls with side-effects should therefore not be eliminatable. This also guarantees that users relying on Initialize effects on non-limited controlled types in analogy to limited controlled types cannot be surprised by optimizations.
Consequently, in the absence of an explicit initialization, the Initialize/Finalize pair will be preserved. With an explicit initialization, the resulting Adjust/Finalize pair can however be eliminated by the proposed permissions.
The optimizations argued for are restricted to those cases where, at Ada source level, an initialization or assignment occurs, but the assigned value is never used, or a "copy propagation" eliminates an intermediate recipient object in the flow of a value from one source to its final destination, where the value of the intermediate object is not used thereafter.
While the above discussion is formulated in terms of pairs of calls for simplicity sake, the real situation is slightly more complicated, since it needs to consider all execution paths.
Consider:
X: Controlled_Type; begin X := something; -- Adjust(X); if P then X := then_something; -- Finalize(X); Adjust(X); else X := else_something; -- Finalize(X); Adjust(X); ... X.Comp -- so that it isn't dead end if; ...
We would like to eliminate the first Adjust call and BOTH Finalize calls. As a group, they constitute the matching pairs. We cannot always eliminate single pairs. It is fairly easy to do in a compiler, but hard to describe in these terms in a language definition.
The words in the !summary therefore capture the bounds of the optimization by its externally visible effects.
Finally, the !question raises an issue with the last sentence of 7.6(21), which indeed is seriously incomplete. The sentence needs to be interpreted to mean that, along with the omission of the re-adjustment, the temporary object is not finalized either. Also, this permission causes a major problem in the case where the object itself is referenced by one of its subcomponents or by other objects reachable via subcomponents and properly modified by the Adjust call to refer to the object in question (e.g., as a means to track all objects of a certain type). The sentence therefore needs to be amended to exclude the optimization in this case.
!appendix

!section 7.6(21)
!subject Can implicit Initialize/Adjust/Finalize pairs be optimized away ?
!reference RM95 7.6(21)
!reference RM95 1.1.3(15)
!from Erhard Ploedereder 96-05-29
!reference 96-5579.a Erhard Ploedereder  96-5-28>>
!discussion

Is it a permissible optimization to omit calls to Initialize, Adjust and
Finalize in connection with declarations, assignments and completions of
masters, when the implementation can determine that these calls are the
only possible source of external effects ?

As a specific example, consider the case of a variable declared to be
of a controlled type with user-defined Initialize and Finalize operations.
This variable is never used. Is is legitimate to omit the Initialize and
Finalize calls for this variable ?

Consider further an assignment to such variable with no subsequent use of
the variable prior to completion of the master. Is it legitimate to omit the
Finalize/Adjust pair of calls along with the value transfer, which would 
normally implement such an assignment ?

Put differently: Can dead code and dead variable elimination disregard 
the effects of such implicit calls in determining whether an object or
assignment is needed at all ?

In the spirit of 7.6(21), which makes the exact number of such calls
implementation-defined, anyhow, one might assume that such liberty causes
little damage, while being quite important for further reducing the number of
such (unneeded) calls and enabling other optimizations. 


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

!section 7.6(21)
!subject Can implicit Initialize/Adjust/Finalize pairs be optimized away ?
!reference RM95 7.6(21)
!reference RM95 1.1.3(15)
!reference 96-5579.a Erhard Ploedereder  96-5-28
!from Norman Cohen  96-5-29
!reference 96-5580.a Norman H. Cohen 96-5-29>>
!discussion

Erhard writes:

 > In the spirit of 7.6(21), which makes the exact number of such calls
 > implementation-defined, anyhow, one might assume that such liberty causes
 > little damage, while being quite important for further reducing the number of
 > such (unneeded) calls and enabling other optimizations.

I agree.  I had thought that 7.6(21) already provided such permission,
but after reading it again, I see that it does not, and a binding
interpretation is needed.


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

!section 7.6(21)
!subject Can implicit Initialize/Adjust/Finalize pairs be optimized away ?
!reference RM95 7.6(21)
!reference RM95 1.1.3(15)
!reference 96-5579.a Erhard Ploedereder  96-5-28
!reference 96-5582.a Robert A Duff 96-5-29>>
!discussion

> Is it a permissible optimization to omit calls to Initialize, Adjust and
> Finalize in connection with declarations, assignments and completions of
> masters, when the implementation can determine that these calls are the
> only possible source of external effects ?

I don't see any permission to *ever* omit an Initialize, nor the
corresponding Finalize.  7.6(18-21) are about omitting Adjust/Finalize
pairs.  We might want to liberalize the rules slightly there, but one
thing I feel strongly is that:

    For *limited* types, what you see is what you get.

That is, the Initialize and Finalize calls that 7.6 and 7.6.1 talks
about really need to happen, for limited types.  For example, a limited
controlled type might be used to lock/unlock a semaphore, and the
compiler should not be allowed to eliminate that code, even if the
limited controlled object is never otherwise used.

For non-limited types, I'm not so sure, but it's probably best to stick
to eliminating Adjust/Finalize pairs, and never eliminating
Initialize/Finalize pairs -- this would achieve the above principle for
limited types, and also for non-limited types that never happen to get
assigned here and there.

> As a specific example, consider the case of a variable declared to be
> of a controlled type with user-defined Initialize and Finalize operations.
> This variable is never used. Is is legitimate to omit the Initialize and
> Finalize calls for this variable ?

If limited, certainly not.  If non-limited, probably not.

> Consider further an assignment to such variable with no subsequent use of
> the variable prior to completion of the master. Is it legitimate to omit the
> Finalize/Adjust pair of calls along with the value transfer, which would 
> normally implement such an assignment ?

Hmm.  Maybe.

> Put differently: Can dead code and dead variable elimination disregard 
> the effects of such implicit calls in determining whether an object or
> assignment is needed at all ?

No.

> In the spirit of 7.6(21), which makes the exact number of such calls
> implementation-defined, anyhow, one might assume that such liberty causes
> little damage, while being quite important for further reducing the number of
> such (unneeded) calls and enabling other optimizations. 

True, but certainly not for limited types.

- Bob


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

!section 7.6(21)
!subject Can implicit Initialize/Adjust/Finalize pairs be optimized away ?
!from Robert Dewar 96-05-30
!reference RM95 7.6(21)
!reference RM95 1.1.3(15)
!reference 96-5579.a Erhard Ploedereder  96-5-28
!reference 96-5582.a Robert A Duff 96-5-29
!reference 96-5586.a Robert Dewar 96-5-30>>
!discussion

Bob Duff said

  I don't see any permission to *ever* omit an Initialize, nor the
  corresponding Finalize.  7.6(18-21) are about omitting Adjust/Finalize
  pairs.  We might want to liberalize the rules slightly there, but one
  thing I feel strongly is that:

    For *limited* types, what you see is what you get.

I agree this is critical. Dummy objects with finalization routines are
an important feature of the language and must work.

The following is just one example:

A surprising thing about Ada 95 is that there
is no convenient way to defer abort, yet in an environment where one is
actually using asynchronous aborts this is crucial.

In GNAT, the pragma Abort_Defer is available, and at least in the case of
one user who tried to use ATC (but has since decided it was a bad idea all
round), they found their program growing full of instances of this pragma.

However, if you are trying to use standard features, you only have two
choices for deferring abort in practice, protected operations, and
finalization operations. For example, suppose I am writing a bubble sort,
and I want it to be asynch safe, in the sense that if it is interrupted
I don't want data loss.

This means that the exchange has to be abort protected. In GNAT one would
just write:

     procedure Exchange (I, J) is
     begin
        pragma Abort_Defer;
        ...
     end;

but if you want to avoid non-standard pragmas, then you either write a
dummy protected record, and pray that your compiler will optimize and
completely remove the junk locks (a very difficult optimization), or
you declare a dummy object to be finalized and make the exchange
procedure be the finalization routine. Both approaches are very kludgy,
but at least the finalization approach should generate semi-reasonable
code (at least avoiding the likely extra kernel calls in the protected
object case).

So, in short, it sure is VERY important that limited types do not mysteriously
disappear as far as initialize and finalize go. Indeed during the language
development, we deliberately decided we could do without block finalization
on the grounds that you can always declare a dummy object and use the
finalization of the dummy object for this purpose.

Actually it is a little obscure that this only works in the limited case,
I don't see the RM justification for this?



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

!section 7.6(21)
!subject Can implicit Initialize/Adjust/Finalize pairs be optimized away ?
!reference RM95 7.6(21)
!reference RM95 1.1.3(15)
!reference 96-5579.a Erhard Ploedereder  96-5-28
!reference 96-5582.a Robert A Duff 96-5-29
!reference 96-5586.a Robert Dewar 96-5-30
!from Bob Duff
!reference 96-5594.a Robert A Duff 96-6-5>>
!discussion

> However, if you are trying to use standard features, you only have two
> choices for deferring abort in practice, protected operations, and
> finalization operations.
...
> but if you want to avoid non-standard pragmas, then you either write a
> dummy protected record, and pray that your compiler will optimize and
> completely remove the junk locks (a very difficult optimization), or
> you declare a dummy object to be finalized and make the exchange
> procedure be the finalization routine. Both approaches are very kludgy,
> but at least the finalization approach should generate semi-reasonable
> code (at least avoiding the likely extra kernel calls in the protected
> object case).

Well, this is a side issue, but: Why not put the abort-deferred code in
an Initialize routine, which is also abort-deferred?  The compiler could
special-case limited controlled types that do not override Finalize, and
generate code that is no less efficient than GNAT's pragma Abort_Defer.
The overhead of controlled types comes from Finalize, not from
Initialize.  That is, if Finalize does nothing, there's no need to hook
objects onto finalization lists and unhook them, and deal with
exceptions and so forth.  This seems like a pretty straightforward
optimization.

> So, in short, it sure is VERY important that limited types do not mysteriously
> disappear as far as initialize and finalize go. Indeed during the language
> development, we deliberately decided we could do without block finalization
> on the grounds that you can always declare a dummy object and use the
> finalization of the dummy object for this purpose.
>
> Actually it is a little obscure that this only works in the limited case,
> I don't see the RM justification for this?

It doesn't -- if you don't do any assignments, so Adjust never happens,
limited and non-limited are equivalent.  The question is, do we want to
change that fact.  I suspect not.  But I do see *some* point in
eliminating pseudo-dead non-limited controlled variables, whereas I see
*no* point in eliminating pseudo-dead *limited* controlled variables
(which may well exist purely for the side effects of their Initialize
and/or Finalize).  So, as far as the RM is concerned, until
"interpreted" otherwise by the ARG, the only permissions to play games
apply to Adjust/Finalize pairs, and not Initialize/Finalize pairs.

- Bob

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

!section 7.6(17)
!subject Can "A:=B" be two assignment operations ?
!reference RM95-7.6(17)
!reference RM95-9.8(11)
!from Erhard Ploedereder 96-06-30
!reference 96-5618.a Erhard Ploedereder  96-6-29>>
!discussion

For controlled types, RM95-7.6(17) describes the canonical semantics of
"A := B" as assigning the value of B to an anonyomous object, adjusting the
value and then assigning the value of the anonymous object to A (plus doing
the finalizations involved).  So, there are really two assignments taking
place.

Is such an (implementation of) "A:=B" one or two assignment operations for
the purposes of 9.8(11) ? Put differently, is "A:=B" an abort-deferred
operation in its entirety or is it possible that an abortion may take place
after the value of the anonymous object is already adjusted, but "A" is as
yet untouched ?

If Adjust or Finalize have side-effects, the question above is semantically
significant to implementers and testers of 9.8(11) -- maybe not so much to
users.

[Note: ACVC-test C980003 wants to know to check abort-deferral of
assignments in general.]

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

!section 7.6(17)
!subject Can "A:=B" be two assignment operations ?
!reference RM95-7.6(17)
!reference RM95-9.8(11)
!reference 96-5618.a Erhard Ploedereder 96-06-30
!from Tucker Taft 96-06-30
!reference 96-5619.a Tucker Taft 96-6-30>>
!discussion

> For controlled types, RM95-7.6(17) describes the canonical semantics of
> "A := B" as assigning the value of B to an anonyomous object, adjusting the
> value and then assigning the value of the anonymous object to A (plus doing
> the finalizations involved).  So, there are really two assignments taking
> place.

Correct, though implementation permissions allow the two to be combined.

> Is such an (implementation of) "A:=B" one or two assignment operations for
> the purposes of 9.8(11) ? Put differently, is "A:=B" an abort-deferred
> operation in its entirety or is it possible that an abortion may take place
> after the value of the anonymous object is already adjusted, but "A" is as
> yet untouched ?

Paragraph 9.8(11) says "assignment operation" not "assignment statement"
so it seems that an abort between the two assignments is perfectly
acceptable.  Of course, the anonymous object needs to get cleaned up
properly.

> If Adjust or Finalize have side-effects, the question above is semantically
> significant to implementers and testers of 9.8(11) -- maybe not so much to
> users.

There are implementation permissions to eliminate Adjusts and Finalizes,
so the side effects had better be benign.

> [Note: ACVC-test C980003 wants to know to check abort-deferral of
> assignments in general.]

-Tuck

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

Questions? Ask the ACAA Technical Agent