!standard 07.06 (21) 99-03-25 AI95-00147/06 !class binding interpretation 96-06-06 !status ARG Approved 6-0-2 99-03-26 !status work item 98-04-01 !status ARG Approved (with changes) 10-1-2 97-11-16 !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 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 Initialize, Adjust and Finalize calls and associated assignment operations on an object of non-limited controlled type if a) any usage of the value of the object after the implicit Initialize or Adjust call and before any subsequent Finalize call on the object does not affect the external effect of any program execution, and b) after the omission of such calls and operations, any execution of the program that executes an Initialize or Adjust call on an object or initializes an object by an aggregate 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 have additional effects. 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 99-02-23 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 ? [No] 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 ? [No] 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); [Yes] 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 99-02-23 For limited controlled types, the canonical semantics apply. For non-limited controlled types, matching pairs of Adjust/Finalize and Initialize/Finalize calls 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 (if any) 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. For an implicit Initialize call, where the initialized value is not read after the Initialize call and prior to the Finalize call for the next assignment to the object or for its destruction, the Initialize/Finalize pair of calls 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 99-02-23 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 (<<>); 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 Initialize/Finalize pairs and 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 discernible 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 is obviously interesting, when a variable is declared, but never used. Or, the more likely case, other optimizations have found such use to be unnecessary. Equally interesting are Adjust/Finalize pairs for an initialized variable that is never used. Consider also, for example, if the user had written "Result: Some_Controlled_Type; ... Result := F;" above, instead of "Result: Some_Controlled_Type := F;". Canonical semantics would then cause a pair of Initialize/Finalize calls on Result, followed by an Adjust call, while the original program caused only the Adjust call. A semantics that makes these two alternatives significantly different, is surely a surprise to many users. Permission to eliminate the Initialize/Finalize pair creates at least the possibility that the two alternatives might result in the same behavior (and acts as minor additional incentive to the programmer to make Initialize and Finalize an "inverse" pair to get identical semantics from both alternatives). 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 96-09-04 !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 **************************************************************** From: Tucker Taft Sent: Tuesday, March 02, 1999 9:55 PM Subject: Re: AI-00147 revised > An implementation is permitted to omit implicit Initialize, 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 I don't find this wording very understandable. You explain things better later. The presumption is that after a Finalize, there is no reference to the value anyway. So all we care about is that between the return from Initialize/Adjust, and the call to Finalize, the value of the object is not used. Another way to put it is that if the Initialize is omitted, then the value is undefined until the next copy/Adjust (if any), and the Initialize can be omitted only if the content of this undefined value does not affect the external interactions of the program up to that next Adjust. This is similar to the permission in 11.6(5) to omit raising an exception upon a check failure. The raise may be omitted only if the content of the undefined value wouldn't alter the external interactions. The key point is that the compiler does *not* need to look "inside" the Initialize, Adjust, or Finalize routine to make this determination. All it needs to notice is whether the content of the object is referenced (in an externally significant way) between the initial Initialize/Adjust call and the matching Finalize. > b) any execution of the program that executes an Initialize or Adjust > call on an object or initializes the object by an aggregate will > also later execute a Finalize call on the object and will always do > so prior to assigning a new value to the object. I also have trouble with this wording. You are implying that an initialize/finalize can be omitted *if* (a) and (b), but I think rather you want to say that "if" (a) is true, and that *after* removing the pair, (b) must still be true. (b) is certainly true *before* you omit the pair, which seems to be all that the word "if" is requiring. > ... -Tuck ****************************************************************