Where are returned values stored? (follow up to yesterday's question)

Where are returned values stored? (follow up to yesterday's question)

[James Alan Farrell]

Hello again,
This is a followup to the question I asked yesterday.  Below is a bit
of code from GNAT's ASIS library.  (I imagine this was written by
people with a lot more expertise in Ada than I have, and that this
code is okay.)

 It has a declarative part in the middle of the code, in which a
variable (Result)  is declared.  The stuff in that variable is
returned.

Now its my understanding that when variables are declared like this,
they are added onto the stack, then when the function returns, they
are popped off again, along with the regular stack frame.  So the
stuff returned goes away.

But, the calling function will need use of that data.  So it cannot go
away.  

So how does that work?  Where is the data placed so that it does not
go away, and how long will it be there so it (or rather pointers to
it) can be passed around to other functions?

(This relates to yesterday's question because  if this works the code
I posted yesterday ought to work)

Thanks again,
James Alan Farrell
GrammaTech


   function Compilation_Units
     (The_Context : in Asis.Context)
      return Asis.Compilation_Unit_List
   is
      Res_Cont_Id    : Context_Id := Get_Cont_Id (The_Context);
      Cont_Tree_Mode : Tree_Mode;
   begin
      Check_Validity (The_Context,
               "Asis.Compilation_Units.Compilation_Units");

      Cont_Tree_Mode := Tree_Processing_Mode (Res_Cont_Id);

      if not (Cont_Tree_Mode = Pre_Created or else
              Cont_Tree_Mode = Incremental)
      then
         Not_Implemented_Yet (Diagnosis =>
                  "Asis.Compilation_Units.Compilation_Units");
      end if;

      Reset_Context (Res_Cont_Id);

      declare
         Result_Len : Natural := Lib_Unit_Decls   (Res_Cont_Id) +
                                 Comp_Unit_Bodies (Res_Cont_Id);
         Result     : Compilation_Unit_List (1 .. Result_Len);
      begin
         for I in 1 .. Result_Len loop
            Result (I) := Get_Comp_Unit
                  (First_Unit_Id + Unit_Id (I) - 1, Res_Cont_Id);
         end loop;
         return Result;
      end;

   exception
      when ASIS_Failed =>
         Add_Call_Information (Outer_Call =>
                     "Asis.Compilation_Units.Compilation_Units");
         raise;
      when others =>
         Raise_ASIS_Failed (Diagnosis =>
                     "Asis.Compilation_Units.Compilation_Units");
   end Compilation_Units;

Re: Where are returned values stored? (follow up to yesterday's question)

[Simon Wright]

James Alan Farrell <anonymous@anonymous.com> writes:

> Now its my understanding that when variables are declared like this,
> they are added onto the stack, then when the function returns, they
> are popped off again, along with the regular stack frame.  So the
> stuff returned goes away.
> 
> But, the calling function will need use of that data.  So it cannot go
> away.  
> 
> So how does that work?  Where is the data placed so that it does not
> go away, and how long will it be there so it (or rather pointers to
> it) can be passed around to other functions?

The simple answer is that it returns a copy of the data, just like
simple variables ..

   int foo()
   {
     // stuff
     {
       int res;
       // stuff
       return res;
     }
     return 3;
   }

There may be a more complicated, implementation-dependent answer
involving secondary stacks, but I see no reason in the language why
you need the concept of pointer in this context. And, however it
works, it will be stack-based, so the data will go away at some point
as the stack is popped.

-- 
Simon Wright                               100% Ada, no bugs.

Re: Where are returned values stored? (follow up to yesterday's question)

[Dmitry A. Kazakov]

On 26 May 2004 21:44:04 +0100, Simon Wright <simon@pushface.org>
wrote:

>James Alan Farrell <anonymous@anonymous.com> writes:
>
>> Now its my understanding that when variables are declared like this,
>> they are added onto the stack, then when the function returns, they
>> are popped off again, along with the regular stack frame.  So the
>> stuff returned goes away.
>> 
>> But, the calling function will need use of that data.  So it cannot go
>> away.  
>> 
>> So how does that work?  Where is the data placed so that it does not
>> go away, and how long will it be there so it (or rather pointers to
>> it) can be passed around to other functions?
>
>The simple answer is that it returns a copy of the data, just like
>simple variables ..
>
>   int foo()
>   {
>     // stuff
>     {
>       int res;
>       // stuff
>       return res;
>     }
>     return 3;
>   }

There is an exception for limited types. They can be returned as well!
So the following is legal:

   type X is limited record ...
   A : X;
   
   function Foo return X is
   begin
      return A;
   end Foo;

Here no copy happens upon return.

>There may be a more complicated, implementation-dependent answer
>involving secondary stacks, but I see no reason in the language why
>you need the concept of pointer in this context. And, however it
>works, it will be stack-based, so the data will go away at some point
>as the stack is popped.

--
Regards,
Dmitry Kazakov
www.dmitry-kazakov.de

Re: Where are returned values stored?

[Marius Amado Alves]

>  It has a declarative part in the middle of the code, in which a
> variable (Result)  is declared.  The stuff in that variable is
> returned.

This is a common idiom. In many languages. Don't think in machine terms,
think in language terms. *Values* are being passed around, not objects. You
are already thinking value (stuff in that variable), so that's good. When
you call the function, you provide a place, usually a variable, to hold the
value.

   Object := Function_Call;

So no worries. The value might have travelled to Japan and back, but that's
the machine business, not the programmer's. Now it's held in your Object,
and that's all you need. This from a function user standpoint. From a
function writer standpoint, well, think value again. When you write

   return Result;

you're passing the value. Under the language contract, the user we'll catch
it. (In Ada he has to catch it, in C he can drop it on the spot.)

Re: Where are returned values stored?

[Warren W. Gay VE3WWG]

Marius Amado Alves wrote:
>> It has a declarative part in the middle of the code, in which a
>>variable (Result)  is declared.  The stuff in that variable is
>>returned.
> 
> This is a common idiom. In many languages. Don't think in machine terms,
> think in language terms. *Values* are being passed around, not objects. You
> are already thinking value (stuff in that variable), so that's good. When
> you call the function, you provide a place, usually a variable, to hold the
> value.
> 
>    Object := Function_Call;
> 
> So no worries. The value might have travelled to Japan and back, but that's
> the machine business, not the programmer's. Now it's held in your Object,
> and that's all you need. This from a function user standpoint. From a
> function writer standpoint, well, think value again. When you write
> 
>    return Result;
> 
> you're passing the value. Under the language contract, the user we'll catch
> it. (In Ada he has to catch it, in C he can drop it on the spot.)

If you're worried about the inefficiency of copying data around,
then I would suggest that the above advice is good. Leave that
up to the compiler/machine team.

If you really must know more than that, then you'll need to look
at the assembler output, but maybe the following explanation
might save you from bothering/worrying about it:

Conceptually, there is _no_ reason a compiler _must_ copy a
return value. Consider a function like:

function Foo return String is
   I : Integer := 23;
   S : String(1..3) := "Bar";
   X : Natural := 0;
begin
   ...
   return S;
end;

To return S, all the compiler needs to do is to extend the
caller's stack frame to claim all the storage up to and
including S (I and S assuming sequential assignment), at
the point when Foo returns (return effectively does
reclaim the storage used for X however).

Then the calling code can reference S as if it were a
local variable.  The space used for I is
wasted at this point, but temporarily, who cares?

Once the compiler knows that the caller's use of the returned
value S is no longer required, the stack frame can be shrunk
back to the original size that it had prior to calling Foo.

Is this done? Is it done by GNAT? I have no idea, but I
suspect that this is done in some places, some of the time,
by some compilers. Perhaps, someone in this group
can confirm/debunk this idea.
-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Where are returned values stored? (follow up to yesterday's question)

[Martin Krischik]

James Alan Farrell wrote:

> Hello again,
> This is a followup to the question I asked yesterday.  Below is a bit
> of code from GNAT's ASIS library.  (I imagine this was written by
> people with a lot more expertise in Ada than I have, and that this
> code is okay.)
> 
>  It has a declarative part in the middle of the code, in which a
> variable (Result)  is declared.  The stuff in that variable is
> returned.
> 
> Now its my understanding that when variables are declared like this,
> they are added onto the stack, then when the function returns, they
> are popped off again, along with the regular stack frame.  So the
> stuff returned goes away.

In addition to the other explanation you should be aware the the way this is
done depends if convention C, Ada or DLL is used.

I have made good experience with passing from Ada to C using convention DLL.

Convention C has not worked with all C compilers on Windows.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Where are returned values stored?

[Martin Krischik]

Marius Amado Alves wrote:

>>  It has a declarative part in the middle of the code, in which a
>> variable (Result)  is declared.  The stuff in that variable is
>> returned.

> So no worries. The value might have travelled to Japan and back, but
> that's the machine business, not the programmer's. 

This is in fact not impossible: Read Annex E for details. ;-).

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Where are returned values stored?

[James Alan Farrell]

Interesting to consider this with a recursive procedure, but yes, it
should work.

JAF

On Thu, 27 May 2004 13:05:06 -0400, "Warren W. Gay VE3WWG"
<ve3wwg@cogeco.ca> wrote:

>
>Conceptually, there is _no_ reason a compiler _must_ copy a
>return value. Consider a function like:
>
>function Foo return String is
>   I : Integer := 23;
>   S : String(1..3) := "Bar";
>   X : Natural := 0;
>begin
>   ...
>   return S;
>end;
>
>To return S, all the compiler needs to do is to extend the
>caller's stack frame to claim all the storage up to and
>including S (I and S assuming sequential assignment), at
>the point when Foo returns (return effectively does
>reclaim the storage used for X however).
>
>Then the calling code can reference S as if it were a
>local variable.  The space used for I is
>wasted at this point, but temporarily, who cares?
>
>Once the compiler knows that the caller's use of the returned
>value S is no longer required, the stack frame can be shrunk
>back to the original size that it had prior to calling Foo.
>
>Is this done? Is it done by GNAT? I have no idea, but I
>suspect that this is done in some places, some of the time,
>by some compilers. Perhaps, someone in this group
>can confirm/debunk this idea.

Re: Where are returned values stored?

[Warren W. Gay VE3WWG]

 > Interesting to consider this with a recursive procedure, but yes, it
 > should work.
 >
 > JAF

Recursive procedures offer no real challenge, except that
if you passed a return value from a deeply nested call,
all the way back down, you could temporarily have
considerable "stack wastage". But there is no reason that
an address comparison couldn't be made and a copy forced
when a certain threshold of waste was reached. OTOH, if the
compiler knows the usage is very short lived, it might
as well just use it where it sits and "release" it after
(especially if no further function/procedure calls are
made, that will need use of the stack).

Calling Conventions:

If this indeed happens (on a given platform), I would think
that the calling convention used is +critical+. For example,
if you forced an Ada routine to use the C calling convention,
I would bet that on most platforms, that all return values
must be _copied_ or placed on the heap (temporarily). At least
this would be true for strings/arrays etc. where the size
was not known in advance.

This is because most platforms (I think), have C
programs pop off their stack frame as part of the
return "process" (I believe this to be true of
Wintel and Linux on Intel for example).

So the compiler might be forced to copy the return
value to some other location, or make some other
arrangement for non Ada calling conventions. You
obviously can't just re-extend the stack frame after
a return because of the possibility of UNIX process
signal calls or interrupt processing that
may overwrite the stack area of interest.

For this reason, I would expect that an Ada calling
convention (when it supports this "return value in
place" concept) probably has the called function Foo,
performing the shrink of its stack frame
as part of the return "processing"; but only enough
to keep the return value protected. The caller then
must finish the job by some prior arrangement known
to the compiler, after the return value is no longer
required.

Just keep in mind that my responses on this thread
are all conceptual/conjecture, and has no documented
factual basis in any existing implementation ;-)

Warren.

James Alan Farrell wrote:
> On Thu, 27 May 2004 13:05:06 -0400, "Warren W. Gay VE3WWG"
> <ve3wwg@cogeco.ca> wrote:
>>Conceptually, there is _no_ reason a compiler _must_ copy a
>>return value. Consider a function like:
>>
>>function Foo return String is
>>  I : Integer := 23;
>>  S : String(1..3) := "Bar";
>>  X : Natural := 0;
>>begin
>>  ...
>>  return S;
>>end;
>>
>>To return S, all the compiler needs to do is to extend the
>>caller's stack frame to claim all the storage up to and
>>including S (I and S assuming sequential assignment), at
>>the point when Foo returns (return effectively does
>>reclaim the storage used for X however).
>>
>>Then the calling code can reference S as if it were a
>>local variable.  The space used for I is
>>wasted at this point, but temporarily, who cares?
>>
>>Once the compiler knows that the caller's use of the returned
>>value S is no longer required, the stack frame can be shrunk
>>back to the original size that it had prior to calling Foo.
>>
>>Is this done? Is it done by GNAT? I have no idea, but I
>>suspect that this is done in some places, some of the time,
>>by some compilers. Perhaps, someone in this group
>>can confirm/debunk this idea.
-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Where are returned values stored?

[Martin Krischik]

Warren W. Gay VE3WWG wrote:

>  > Interesting to consider this with a recursive procedure, but yes, it
>  > should work.
>  >
>  > JAF
> 
> Calling Conventions:
> 
> If this indeed happens (on a given platform), I would think
> that the calling convention used is +critical+. For example,
> if you forced an Ada routine to use the C calling convention,
> I would bet that on most platforms, that all return values
> must be _copied_ or placed on the heap (temporarily). At least
> this would be true for strings/arrays etc. where the size
> was not known in advance.

The "C" calling convention places the return value inside a hidden static
variable. A pointer to this variable is then returned.

So you correctly observed: size need to be known at compile time. Also: this
is not multi tasking capable.

> This is because most platforms (I think), have C
> programs pop off their stack frame as part of the
> return "process" (I believe this to be true of
> Wintel and Linux on Intel for example).

On Windows the most used calling convention is not "C" bot "DLL" or "API".
With calling convention "DLL" the caller reserves space for the return
variable on the stack and passes a pointer to that space.

Again: not good for indefinite types.

> So the compiler might be forced to copy the return
> value to some other location, or make some other
> arrangement for non Ada calling conventions. You
> obviously can't just re-extend the stack frame after
> a return because of the possibility of UNIX process
> signal calls or interrupt processing that
> may overwrite the stack area of interest.

GNAT will warn you if you pass indefinite types with either "C" or "DLL"
calling convention.

> Just keep in mind that my responses on this thread
> are all conceptual/conjecture, and has no documented
> factual basis in any existing implementation ;-)

My are practical experience on Linux/Windows with GNAT. It might be
different for other Platforms.

If you need to return complex types between Ada and C I would suggest
calling convention "DLL". GNAT Linux understands calling convention "DLL"
as well and will do the right thing.

With Regards

Martin
-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Where are returned values stored?

[Larry Kilgallen]

In article <60328483.MtZnWf8h2m@linux1.krischik.com>, Martin Krischik <krischik@users.sourceforge.net> writes:
> Warren W. Gay VE3WWG wrote:
> 
>>  > Interesting to consider this with a recursive procedure, but yes, it
>>  > should work.
>>  >
>>  > JAF
>> 
>> Calling Conventions:
>> 
>> If this indeed happens (on a given platform), I would think
>> that the calling convention used is +critical+. For example,
>> if you forced an Ada routine to use the C calling convention,
>> I would bet that on most platforms, that all return values
>> must be _copied_ or placed on the heap (temporarily). At least
>> this would be true for strings/arrays etc. where the size
>> was not known in advance.

Just jumping in, this seems to be an OS-independent discussion.

> The "C" calling convention places the return value inside a hidden static
> variable. A pointer to this variable is then returned.

I am not sure what you mean by "the" C calling convention.

Certainly on VMS C obeys the OS calling convention for all inter-module
calls, just as other languages do.

Re: Where are returned values stored?

[Martin Krischik]

Larry Kilgallen wrote:

> In article <60328483.MtZnWf8h2m@linux1.krischik.com>, Martin Krischik
> <krischik@users.sourceforge.net> writes:
>> Warren W. Gay VE3WWG wrote:
>> 
>>>  > Interesting to consider this with a recursive procedure, but yes, it
>>>  > should work.
>>>  >
>>>  > JAF
>>> 
>>> Calling Conventions:
>>> 
>>> If this indeed happens (on a given platform), I would think
>>> that the calling convention used is +critical+. For example,
>>> if you forced an Ada routine to use the C calling convention,
>>> I would bet that on most platforms, that all return values
>>> must be _copied_ or placed on the heap (temporarily). At least
>>> this would be true for strings/arrays etc. where the size
>>> was not known in advance.
> 
> Just jumping in, this seems to be an OS-independent discussion.

The OP is involved in C - Ada mixed language programming.

>> The "C" calling convention places the return value inside a hidden static
>> variable. A pointer to this variable is then returned.
> 
> I am not sure what you mean by "the" C calling convention.

Whatever K&R though is practical for there programming language. For use
from Ada see also RM B.3 (1/1).

> Certainly on VMS C obeys the OS calling convention for all inter-module
> calls, just as other languages do.

As does Windows and OS/2. It seems that almost everywhere the C compilers
don't use calling convention "C" anymore for anything but printf and scanf.

With Regards

Martin

-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Where are returned values stored?

[Nick Roberts]

"Warren W. Gay VE3WWG" <ve3wwg@cogeco.ca> wrote in message
news:1dptc.49822$tb4.1731604@news20.bellglobal.com...

> If you're worried about the inefficiency of copying data around,
> then I would suggest that the above advice is good. Leave that
> up to the compiler/machine team.
>
> If you really must know more than that, then you'll need to look
> at the assembler output, but maybe the following explanation
> might save you from bothering/worrying about it:
>
> Conceptually, there is _no_ reason a compiler _must_ copy a
> return value. Consider a function like:
>
> function Foo return String is
>    I : Integer := 23;
>    S : String(1..3) := "Bar";
>    X : Natural := 0;
> begin
>    ...
>    return S;
> end;
>
> To return S, all the compiler needs to do is to extend the
> caller's stack frame to claim all the storage up to and
> including S (I and S assuming sequential assignment), at
> the point when Foo returns (return effectively does
> reclaim the storage used for X however).
>
> Then the calling code can reference S as if it were a
> local variable.  The space used for I is
> wasted at this point, but temporarily, who cares?
>
> Once the compiler knows that the caller's use of the returned
> value S is no longer required, the stack frame can be shrunk
> back to the original size that it had prior to calling Foo.
>
> Is this done? Is it done by GNAT? I have no idea, but I
> suspect that this is done in some places, some of the time,
> by some compilers. Perhaps, someone in this group
> can confirm/debunk this idea.

I don't think any compiler does quite as you suggest, Warren, but many do
something similar: they allocate two stacks to each task, usually called the
'primary' and 'secondary' stacks; the primary stack is used as the normal
stack, and the secondary is used exclusively for returning indefinite
function results.

In the common case of all the return statements in a function being of the
form 'return S' (as above), S will be allocated on the secondary stack. When
Foo returns, its stack frame (containing I and X plus some other stuff) is
deallocated (from the primary stack), but the calling code can access the
result (S) on the secondary stack. When the calling code has finished with
S, it deallocates it (from the secondary stack).

In the general case (return statements returning expressions), an anonymous
intermediate variable is used instead of S, and it is this anonymous
variable that is allocated on the secondary stack.

You can see that this works fine for recursive functions, although a
rewriting (so it is no longer recursive) of a recursive function that
returns an indefinite type may produce a much more memory-efficient
algorithm.

The only problem is that you have two stacks per task. That can add up to a
lot of stacks for some programs! One optimisation is to determine if a task
will never call a function that needs a secondary stack, and eliminate the
(allocation of) the secondary stack for such tasks; if my memory serves me,
I think I've heard of an Ada compiler that does this optimisation.

I think all those compilers which don't use a secondary stack use the heap
(or some storage pool) instead.

-- 
Nick Roberts

Re: Where are returned values stored?

[Warren W. Gay VE3WWG]

Nick Roberts wrote:
> "Warren W. Gay VE3WWG" <ve3wwg@cogeco.ca> wrote in message
> news:1dptc.49822$tb4.1731604@news20.bellglobal.com...
...
>>Conceptually, there is _no_ reason a compiler _must_ copy a
>>return value. Consider a function like:
>>
>>function Foo return String is
>>   I : Integer := 23;
>>   S : String(1..3) := "Bar";
>>   X : Natural := 0;
>>begin
>>   ...
>>   return S;
>>end;
>>
>>To return S, all the compiler needs to do is to extend the
>>caller's stack frame to claim all the storage up to and
>>including S (I and S assuming sequential assignment), at
>>the point when Foo returns (return effectively does
>>reclaim the storage used for X however).
>>
>>Then the calling code can reference S as if it were a
>>local variable.  The space used for I is
>>wasted at this point, but temporarily, who cares?
>>
>>Once the compiler knows that the caller's use of the returned
>>value S is no longer required, the stack frame can be shrunk
>>back to the original size that it had prior to calling Foo.
>>
>>Is this done? Is it done by GNAT? I have no idea, but I
>>suspect that this is done in some places, some of the time,
>>by some compilers. Perhaps, someone in this group
>>can confirm/debunk this idea.
> 
> I don't think any compiler does quite as you suggest, Warren, but many do
> something similar: they allocate two stacks to each task, usually called the
> 'primary' and 'secondary' stacks; the primary stack is used as the normal
> stack, and the secondary is used exclusively for returning indefinite
> function results.

I cannot say for sure about the "in practice" aspect, since
I've never troubled myself to find out. But a second stack
seems to me to be an expensive way to solve the problem. It
certainly wouldn't be my first choice, if I were implementing
a compiler.

However, I can see how that could solve the problem if the
calling contention(s) available on a given hardware platform
demanded it.

A 2nd stack would mean fragmenting your memory space even
more, requiring a extra level of planning. Determining
stack requirements is always tricky when you have
subprograms that recurse. Otherwise static analysis would
be sufficient.

> In the general case (return statements returning expressions), an anonymous
> intermediate variable is used instead of S, and it is this anonymous
> variable that is allocated on the secondary stack.

Yes of course, since the same principle is at work.

> The only problem is that you have two stacks per task. That can add up to a
> lot of stacks for some programs! One optimisation is to determine if a task
> will never call a function that needs a secondary stack, and eliminate the
> (allocation of) the secondary stack for such tasks; if my memory serves me,
> I think I've heard of an Ada compiler that does this optimisation.
> 
> I think all those compilers which don't use a secondary stack use the heap
> (or some storage pool) instead.

It would be nice to have a survey of the different compilers
and methods used. So far we've not successfully trolled the
compiler vendors in CLA into saying more on the topic ;-)
-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Where are returned values stored?

[Robert I. Eachus]

Warren W. Gay VE3WWG wrote:

> If this indeed happens (on a given platform), I would think
> that the calling convention used is +critical+. For example,
> if you forced an Ada routine to use the C calling convention,
> I would bet that on most platforms, that all return values
> must be _copied_ or placed on the heap (temporarily). At least
> this would be true for strings/arrays etc. where the size
> was not known in advance.
> 
> This is because most platforms (I think), have C
> programs pop off their stack frame as part of the
> return "process" (I believe this to be true of
> Wintel and Linux on Intel for example).
> 
> So the compiler might be forced to copy the return
> value to some other location, or make some other
> arrangement for non Ada calling conventions. You
> obviously can't just re-extend the stack frame after
> a return because of the possibility of UNIX process
> signal calls or interrupt processing that
> may overwrite the stack area of interest.
> 
> For this reason, I would expect that an Ada calling
> convention (when it supports this "return value in
> place" concept) probably has the called function Foo,
> performing the shrink of its stack frame
> as part of the return "processing"; but only enough
> to keep the return value protected. The caller then
> must finish the job by some prior arrangement known
> to the compiler, after the return value is no longer
> required.

Several Ada compilers used a two-stack strategy.  One was the normal 
call stack, and the other was mostly for function return values.  Since 
you only needed to create things on the second stack for functions with 
return values that were not passed in registers, the overhead only 
appeared when you did have such functions.  And the compilers were 
'smart' enough to do any necessary splicing of values correctly.

So a function fubar returning "foo(x) & bar(y)" where foo and bar were 
functions returning strings would pass the descriptors in registers or 
as part of the calling sequence on the first stack.  Only the characters 
in the strings would go on the second stack, and of course fubar would 
just do the descriptor arithmetic and not touch the second stack at all.

I think Softech's ALS had a variation, on the two stack approach, but I 
didn't think much of it.  They used ping-pong stacks.  There were two 
stacks but the stack frames for the caller and callee were always on 
different stacks.  That way the caller could inspect the whole stack 
frame of a function that had just returned if necessary--but all it did 
was look for the location of the return value and also for the 
descriptor information if necessary.  However, in the case of nested 
calls with variable sized arguments returned through, the return values 
  had to be copied back and forth.

-- 

                                           Robert I. Eachus

"The terrorists rejoice in the killing of the innocent, and have 
promised similar violence against Americans, against all free peoples, 
and against any Muslims who reject their ideology of murder. Their 
barbarism cannot be appeased, and their hatred cannot be satisfied. 
There's only one way to deal with terror: We must confront the enemy and 
stay on the offensive until these killers are defeated." -- George W. Bush

Re: Where are returned values stored?

[Robert I. Eachus]

Warren W. Gay VE3WWG wrote:

> A 2nd stack would mean fragmenting your memory space even
> more, requiring a extra level of planning. Determining
> stack requirements is always tricky when you have
> subprograms that recurse. Otherwise static analysis would
> be sufficient.

You are thinking like an embedded programmer, and probably should be 
using SPARK.  In a virtual memory environment, things are much 
different. I've lived in both worlds. If you make tasks "heavy" threads, 
with their own virtual address space, the number of stacks and their 
size is a non-issue.  On compilers where tasks are lightweight (all 
share a single address space) you can't be quite so free with addresses. 
  But it usually suffices to materialize a minimum return stack if per 
task if and when it is referenced, and leave it unallocated otherwise. 
Of course, if a function returns a huge number of bytes, you allocate 
the space from the heap, and put a descriptor on the return stack.

The definitions of minimum return stack size and huge are of course 
compiler dependent.  And of course it is a bit of a pain if you have to 
grow the return stack by copying.  (The return stack can contain 
addresses, but references into locations in the return stack have to be 
offsets.  That way you can copy it if needed to expand it.)  But 
definitions like an 8 kByte startiing size and treating anything over 1 
kByte as 'huge' work pretty well.

This is a side-effect of the Ada culture.  Although Ada allows returning 
huge objects, for any meaning of huge, from functions and allocating 
huge object in stack frames, it turns out that in practice most huge 
arrays get allocated in package specs or bodies.  When we were creating 
the Ada/SIL compiler a lot of things were postponed until we actually 
ran into them.  We went for months without deciding what to do when any 
stack exceeded 128 kBytes.  Final decision?  Raise Storage_Error.  The 
few logged cases of running into this limit were all accidental 
indefinite recursion, or attempts to allocate a maximum size String 
(2**31-1 bytes) or other maximum size array.

Alsys has/had, whatever the name is now for the French compiler, a limit 
of 8 kBytes that was pretty similar.  If an object type had an 
indefinite size that could be greater than 8 k, it would go on the heap 
with a descriptor on the stack.  It allowed them to support indefinite 
record types (records with discriminants that have defaults and 
composite components whose bounds depend on one or more discriminants, 
where the object is declared without a discriminant constraint).  Alsys 
used the name mutant records, and it became associated with their method 
of managing such objects more than the object types themselves.  It 
really would be handy if such records had a short meaningful name...

-- 

                                           Robert I. Eachus

"The terrorists rejoice in the killing of the innocent, and have 
promised similar violence against Americans, against all free peoples, 
and against any Muslims who reject their ideology of murder. Their 
barbarism cannot be appeased, and their hatred cannot be satisfied. 
There's only one way to deal with terror: We must confront the enemy and 
stay on the offensive until these killers are defeated." -- George W. Bush

Re: Where are returned values stored?

[Warren W. Gay VE3WWG]

Robert I. Eachus wrote:
> Warren W. Gay VE3WWG wrote:
>> A 2nd stack would mean fragmenting your memory space even
>> more, requiring a extra level of planning. Determining
>> stack requirements is always tricky when you have
>> subprograms that recurse. Otherwise static analysis would
>> be sufficient.
> 
> You are thinking like an embedded programmer, and probably should be 
> using SPARK.  

I would disagree, but this is unimportant ;-)

> In a virtual memory environment, things are much 
> different. I've lived in both worlds. If you make tasks "heavy" threads, 
> with their own virtual address space, the number of stacks and their 
> size is a non-issue.  

In a POSIX environment, this would be normally called a
"process" -- not a thread. But a quick perusal of
the word "thread" in technical dictionaries online,
seems to return an array of muddled definitions
for "thread".

Threads of course can be implemented with differing
levels of sharing, and one possibility is to not share the
stack address space.

Anyway, I tend to live in the POSIX world, and so for
me at least, more stacks means carving up more of the
precious 2GB address space on 32 bit platforms. Once
everyone moves to 64 bit processors, then this is less
of a problem.

> On compilers where tasks are lightweight (all 
> share a single address space) you can't be quite so free with addresses. 

This is precisely the scenario that I was concerned
about (worst case scenario).

>  But it usually suffices to materialize a minimum return stack if per 
> task if and when it is referenced, and leave it unallocated otherwise. 

Yes, of course.  You must still however, carve up the
address space for the stacks, whether the vm pages are
allocated or not.

 >...

otherwise, interesting comments.
-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Where are returned values stored?

[Nick Roberts]

"Warren W. Gay VE3WWG" <ve3wwg@cogeco.ca> wrote in message
news:AWjvc.22009$Hn.791710@news20.bellglobal.com...

> Robert I. Eachus wrote:
> > ...
> > You are thinking like an embedded programmer, and probably
> > should be  using SPARK.
>
> I would disagree, but this is unimportant ;-)
>
> > In a virtual memory environment, things are much  different. I've
> > lived in both worlds. If you make tasks "heavy" threads, with
> > their own virtual address space, the number of stacks and their
> > size is a non-issue.
>
> In a POSIX environment, this would be normally called a
> "process" -- not a thread. But a quick perusal of
> the word "thread" in technical dictionaries online,
> seems to return an array of muddled definitions
> for "thread".

Indeed, and in some cases it is actually quite hard to say whether threads
really share memory or not.

> Threads of course can be implemented with differing
> levels of sharing, and one possibility is to not share the
> stack address space.
>
> Anyway, I tend to live in the POSIX world, and so for
> me at least, more stacks means carving up more of the
> precious 2GB address space on 32 bit platforms.

You may perhaps be interested to note that my design for the AdaOS kernel
(called 'Bachar') for the IA-32 makes use of segments to help alleviate the
problem.

Because each stack is in its own segment, it can be 'moved' (within the
underlying linear address space) without affecting the addresses of items on
the stack. Because stacks can be moved, it is feasible to start every stack
small and simply grow it as demand requires, even if this requires it to
grow 'huge' (100s of MB) sometimes. I like the way this avoids the necessity
for allocating big or indefinite things on the heap. (And by keeping stacks
page aligned, I can use trickery to move them rapidly.) Using segments
brings problems, but I am learning that it brings some advantages too!

> Once everyone moves to 64 bit processors, then this
> is less of a problem.

Hehe. In fact, 64-bit technology brings the prospect of objects remaining
allocated in virtual memory for years, even decades, maybe even centuries.
It's weird to think that I could compile a DSO into a certain address in
Linux-64 today, and some program written in 200 years' time will refer to it
/at the same address/, when trains run from planet to planet and people run
on batteries.

> > On compilers where tasks are lightweight (all share a
> > single address space) you can't be quite so free with
> > addresses.
>
> This is precisely the scenario that I was concerned
> about (worst case scenario).
>
> >  But it usually suffices to materialize a minimum return
> > stack if per task if and when it is referenced, and leave
> > it unallocated otherwise.
>
> Yes, of course.  You must still however, carve up the
> address space for the stacks, whether the vm pages are
> allocated or not.

There we are. Using segments on the IA-32 gives me 45 bits of address space,
rather than just 32.

-- 
Nick Roberts

Re: Where are returned values stored?

[Robert I. Eachus]

Warren W. Gay VE3WWG wrote:

> In a POSIX environment, this would be normally called a
> "process" -- not a thread. But a quick perusal of
> the word "thread" in technical dictionaries online,
> seems to return an array of muddled definitions
> for "thread".

I often use process that way to.  The choices seem to be light and 
heavyweight processes, light and heavy threads, or threads and proceses. 
  For this discussion, I thought the emphasis should be on whether or 
not address space was shared, so I chose the terms I did.  (There can 
also be scheduling differences between processes and threads, and that 
is irrelevant here.)

> Anyway, I tend to live in the POSIX world, and so for
> me at least, more stacks means carving up more of the
> precious 2GB address space on 32 bit platforms. Once
> everyone moves to 64 bit processors, then this is less
> of a problem.

I'm shopping for an Athlon64 right now, and exactly for this reason. ;-)

>>  But it usually suffices to materialize a minimum return stack if per 
>> task if and when it is referenced, and leave it unallocated otherwise. 
> 
> 
> Yes, of course.  You must still however, carve up the
> address space for the stacks, whether the vm pages are
> allocated or not.

Actually, no.  There is one of those obvious in hindsight neat tricks. 
Don't allocate the address space for the stack and leave the pointer to 
the stack null/invalid.  When the stack needs to be used, both the 
address space and physical space have to be allocated and can then be 
used.  This helps a lot in Ada, where most tasks will never need or use 
the return stack.

-- 

                                           Robert I. Eachus

"The terrorists rejoice in the killing of the innocent, and have 
promised similar violence against Americans, against all free peoples, 
and against any Muslims who reject their ideology of murder. Their 
barbarism cannot be appeased, and their hatred cannot be satisfied. 
There's only one way to deal with terror: We must confront the enemy and 
stay on the offensive until these killers are defeated." -- George W. Bush

Re: Where are returned values stored?

[Warren W. Gay VE3WWG]

Robert I. Eachus wrote:

> Warren W. Gay VE3WWG wrote:
>> Anyway, I tend to live in the POSIX world, and so for
>> me at least, more stacks means carving up more of the
>> precious 2GB address space on 32 bit platforms. Once
>> everyone moves to 64 bit processors, then this is less
>> of a problem.
> 
> I'm shopping for an Athlon64 right now, and exactly for this reason. ;-)

:)

>>>  But it usually suffices to materialize a minimum return stack if per 
>>> task if and when it is referenced, and leave it unallocated otherwise. 
>>
>> Yes, of course.  You must still however, carve up the
>> address space for the stacks, whether the vm pages are
>> allocated or not.
> 
> Actually, no.  There is one of those obvious in hindsight neat tricks. 

When I wrote this, I had a feeling that you would reply with
this. Agreed again, that you can of course defer the allocation
of the address space along with the vm pages.  But the real point
I was making is that you still have to carve up double the
address space required for stacks, for all "active" tasks.

> used.  This helps a lot in Ada, where most tasks will never need or use 
> the return stack.

True this can help. But if you are planning for
the worst case, then you still have to plan as if all stacks (tasks)
are required. It doesn't help any when you run out of
address space, when the requirements demand it.  Or worse,
if the code is silly enough not to detect it and overlap with
other important memory regions ;-)

-- 
Warren W. Gay VE3WWG
http://home.cogeco.ca/~ve3wwg

Re: Where are returned values stored?

[Nick Roberts]

"Robert I. Eachus" <rieachus@comcast.net> wrote in message
news:fP2dnc8B4Y6kNyPdRVn-hA@comcast.com...

> Warren W. Gay VE3WWG wrote:
> > ...
> > Yes, of course.  You must still however, carve up the
> > address space for the stacks, whether the vm pages are
> > allocated or not.
>
> Actually, no.  There is one of those obvious in hindsight neat
> tricks. Don't allocate the address space for the stack and leave
> the pointer to the stack null/invalid.  When the stack needs to
> be used, both the address space and physical space have to be
> allocated and can then be used.  This helps a lot in Ada, where
> most tasks will never need or use the return stack.

Um, I think this is one of those comments that needs to be taken with a
pinch of salt :-)

Are you (Robert) talking about the main (control, primary) stack? I suspect
most (in fact, all) tasks will use this, even if not much. The IA-32
actually demands the existence of a valid stack (SS:ESP must be valid)
before it will execute anything. I suppose this trick could be used with a
secondary stack. I suppose it could apply to tasks prior to the start of
their execution.

However, it doesn't really detract form the point that, when the stacks
/are/ used, they must be allocated somewhere in your address space.

-- 
Nick Roberts

Re: Where are returned values stored?

[Simon Wright]

"Warren W. Gay VE3WWG" <ve3wwg@cogeco.ca> writes:

> Anyway, I tend to live in the POSIX world, and so for
> me at least, more stacks means carving up more of the
> precious 2GB address space on 32 bit platforms. Once
> everyone moves to 64 bit processors, then this is less
> of a problem.

2GB! I wish! These stacks need to come out of physical RAM (VxWorks
5.5), you don't get 2 GB on a VME single-board computer (well, perhaps
tomorrow).

-- 
Simon Wright                               100% Ada, no bugs.

Re: Where are returned values stored?

[Robert I. Eachus]

Nick Roberts wrote:

> Are you (Robert) talking about the main (control, primary) stack? I suspect
> most (in fact, all) tasks will use this, even if not much. The IA-32
> actually demands the existence of a valid stack (SS:ESP must be valid)
> before it will execute anything. I suppose this trick could be used with a
> secondary stack. I suppose it could apply to tasks prior to the start of
> their execution.

The secondary stack.  Ada task that don't need a primary stack are 
usually now replaced by protected objects, which don't have a stack of 
their own.

> However, it doesn't really detract form the point that, when the stacks
> /are/ used, they must be allocated somewhere in your address space.

But my point was that it is a consequence of good software engineering 
in Ada that very few tasks ever need the secondary stack.

This is a "meta-point" that needs to be made again and again.  Ada 
compilers use many 'solutions' that assume that "under normal 
circumstances" performance will be fine.  Normal circumstances for Ada 
includes decent software engineering practice.  There are lots of 
'newbie' questions, like this one, where the answer has to reference 
software engineering practice to describe WHY things are done the way 
they are done.

In this case, the assumption is that in Ada, functions do not normally 
return 'large' objects, but that large is defined in terms of 
performance in the execution environment, not some arbitrary limit.  So 
if a program uses some function that returns a multi-megabyte String, in 
some execution environments this will be a problem.  But if Integer is a 
32-bit type, the language will allow you to try to return a 2 Gigabyte 
String.  On most hardware, you will fail, but if you are running your 
program on a 64-bit system with more 4 Gigs of memory, performance won't 
be bad at all.

Of course the right thing to do for 'huge' Strings is to put them in 
records, and if necessary go the extra effort to return not the record 
but an access type designating it.  In practice though, these huge 
Strings are not manipulated that way.  You use Unbounded_String, and the 
implementation does the necessary magic for you.

-- 

                                           Robert I. Eachus

"The terrorists rejoice in the killing of the innocent, and have 
promised similar violence against Americans, against all free peoples, 
and against any Muslims who reject their ideology of murder. Their 
barbarism cannot be appeased, and their hatred cannot be satisfied. 
There's only one way to deal with terror: We must confront the enemy and 
stay on the offensive until these killers are defeated." -- George W. Bush

Re: Where are returned values stored?

[Larry Kilgallen]

In article <fpadncjkKI4MV17dRVn-uQ@comcast.com>, "Robert I. Eachus" <rieachus@comcast.net> writes:

> This is a "meta-point" that needs to be made again and again.  Ada 
> compilers use many 'solutions' that assume that "under normal 
> circumstances" performance will be fine.  Normal circumstances for Ada 
> includes decent software engineering practice.  There are lots of 
> 'newbie' questions, like this one, where the answer has to reference 
> software engineering practice to describe WHY things are done the way 
> they are done.
> 
> In this case, the assumption is that in Ada, functions do not normally 
> return 'large' objects, but that large is defined in terms of 
> performance in the execution environment, not some arbitrary limit.  So 
> if a program uses some function that returns a multi-megabyte String, in 
> some execution environments this will be a problem.  But if Integer is a 
> 32-bit type, the language will allow you to try to return a 2 Gigabyte 
> String.  On most hardware, you will fail, but if you are running your 
> program on a 64-bit system with more 4 Gigs of memory, performance won't 
> be bad at all.

Merely having hardware capable of 64-bit addressing does not speed the
copying of that 2 Gigabyte string, so performance might be awful.  On
the other hand, there is a greater likelyhood the program will run to
completion, which is a correctness issue.

Re: Where are returned values stored?

[Robert I. Eachus]

Larry Kilgallen wrote:

> Merely having hardware capable of 64-bit addressing does not speed the
> copying of that 2 Gigabyte string, so performance might be awful.  On
> the other hand, there is a greater likelyhood the program will run to
> completion, which is a correctness issue.

I don't know if you missed the point or not.  Yes, it is a correctness 
issue, and all Ada compiler developers will choose an implementation 
model which is correct over one that is 'mostly' correct and faster. 
But there is an implicit expectation that the programmers understand 
these issues well enough to choose a solution which is both correct, and 
tolerant of these 'hidden' assumptions.

For example, if I write a program to 'read a file a line at a time.'  If 
I don't either know what system enforced maximum line length is or 
choose a arbitrary length and change algorithms for lines longer than 
that length, I have failed to use good software engineering practice.

Notice that there is no inherent 'magic number' for when a line gets 
processed differently.  I tend to use 132 characters, some people I know 
prefer 253, or 255, or 1023.  The actual number doesn't matter that 
much.  Just that you know you won't have nasty problems if someone gives 
you a non-text file.

Similarly, Ada allows me to put arbitrary objects on the stack at 
run-time.  But that means that it is my responsibility as a software 
engineer to insure that the stack won't overflow.  There are often only 
one or two declarations that I have to "worry about" in a program, but 
IMHO knowing which ones those are and how to do the necessary analysis 
is software engineering, not programming.

This is why I used to say that learning Ada is 95% software engineering 
and 5% syntax.  This analysis is often don't "off to one side" and at 
best results in a one-line comment in the source code.  But Ada puts the 
onus of doing this sort of thinking directly on the programmer.  Ada 
makes implementing whatever you decide easy.  But it can't decide for you.

I used to teach that when these situations come up, Ada asks you a 
question.  There was a discussion here about Apples and Oranges the 
other day which illustrates my point exactly.  If the requirements say 
count "at least 100" apples, how do you define the subtype?  There will 
be an upper bound, but it is up to the programmer to choose a sensible one.

-- 

                                           Robert I. Eachus

"The terrorists rejoice in the killing of the innocent, and have 
promised similar violence against Americans, against all free peoples, 
and against any Muslims who reject their ideology of murder. Their 
barbarism cannot be appeased, and their hatred cannot be satisfied. 
There's only one way to deal with terror: We must confront the enemy and 
stay on the offensive until these killers are defeated." -- George W. Bush