Seems like the double * and double ** are put on stack in reverse order expected

[Bob Langelaan]

This output below is produced using MS VS 2105 in Release mode.

Any idea as to why it appears that the double ** variable is put on stack before the double * variable ?

Program:

#include <iostream>
using namespace std;

int main()
{
double myArray[10]; // define an array of 10 doubles
cout << "Address of myArray is: " << myArray;

double * dblePtr; // define a pointer to double
double ** dblePtrToPtr; // define a pointer to a pointer of type double

cout << "\n\nAddress of dblePtr is: " << &dblePtr;
cout << "\n\nAddress of dblePtrToPtr is: " << &dblePtrToPtr;

cout << "\n\nSize of dblePtr: " << sizeof dblePtr;

cout << endl;
return 0;

}

OUTPUT:


Address of myArray is: 0033FE10

Address of dblePtr is: 0033FE08

Address of dblePtrToPtr is: 0033FE0C

Size of dblePtr: 4
Press any key to continue . . .

[Jens Thoms Toerring]

Bob Langelaan <bobl...@gmail.com> wrote:
> This output below is produced using MS VS 2105 in Release mode.

> Any idea as to why it appears that the double ** variable is put on stack
>before the double * variable ?

> #include <iostream>
> using namespace std;

> int main()
> {
> double myArray[10]; // define an array of 10 doubles
> cout << "Address of myArray is: " << myArray;

> double * dblePtr; // define a pointer to double
> double ** dblePtrToPtr; // define a pointer to a pointer of type double

> cout << "\n\nAddress of dblePtr is: " << &dblePtr;
> cout << "\n\nAddress of dblePtrToPtr is: " << &dblePtrToPtr;

> cout << "\n\nSize of dblePtr: " << sizeof dblePtr;
>
> cout << endl;
> return 0;

> }

> OUTPUT:
> Address of myArray is: 0033FE10
> Address of dblePtr is: 0033FE08
> Address of dblePtrToPtr is: 0033FE0C

Why do you care? There's no rule in the standard that would require
the compiler/linker to put the variables in any order into memory
(and if you hadn't printed the addresses they may even never have
been in memory at all but just in CPU registers)?

All this is absolutely at the discretion of the compiler and
using different compiler flags or a different version could re-
sult in a completely different picture.

To be honest, being curious I have done the same kind of tests more
than once;-) And in most cases (not with MS VS) the results were
similar. Since I haven't looked at the compilers sources I can only
guess: the parser uses a stack onto which it pushes each variable
to be defined. And when the end of the function is reached it makes
room for them, popping them from the stack, so the last one defined
becomes first one on the programs stack. But that's pure guesswork
and not backed by any hard facts!

Regards, Jens
--
\ Jens Thoms Toerring ___ j...@toerring.de
\__________________________ http://toerring.de

[Bob Langelaan]

On Saturday, April 16, 2016 at 2:54:18 PM UTC-7, Jens Thoms Toerring wrote:

Thanks for your reply.

Can I assume if instead of defining pointers we were defining objects with associated dtors, that they would always be put on the stack in the expected order to ensure that the dtors are invoked in the correct order?

[Barry Schwarz]

I doubt it. What is the relationship you see between location and
invocation?

--
Remove del for email

[Paavo Helde]

Order of destruction is guaranteed by the standard, but this has nothing
whatsoever to do with the addresses of the variables in memory. In
particular, in your example there are no destructors involved; the
results might be different if you used objects with real destructors.

hth
Paavo

[Jens Thoms Toerring]

qBob Langelaan <bobl...@gmail.com> wrote:
> Can I assume if instead of defining pointers we were defining objects with
> associated dtors, that they would always be put on the stack in the expected
> order to ensure that the dtors are invoked in the correct order?

Sorry, but you can't. The compiler can, more ore less, put any
object whereever it likes. Actually, neither the C nor C++ stan-
dard even mandate that there's a stack at all, so how could be
there a requirement on how things have to be organized on the
stack? And what is an "expected order"? I have no idea what that
would be.

Please take a step back and tell what you want to achieve by re-
lying on some objects being ordered in a certain way on the stack.
You may get away with that with a certain version of a compiler,
when using a certain set of compiler flags, on a certain version
of an operationg system. But any small change in any of these
parameters may invalidate everything that you may have found out
about the compilers behaviour experimentally. Better stay away
from that unless you have very, very good reasons to do it any-
way.

[Alf P. Steinbach]

On 17.04.2016 01:05, Jens Thoms Toerring wrote:
> qBob Langelaan <bobl...@gmail.com> wrote:
>> Can I assume if instead of defining pointers we were defining
>> objects with associated dtors, that they would always be put on the
>> stack in the expected order to ensure that the dtors are invoked in
>> the correct order?
>
> Sorry, but you can't.

Right.

> The compiler can, more ore less, put any object whereever it likes.

C++ provides a guaranteed ordering for data members with the same access
level.


> Actually, neither the C nor C++ standard even mandate that there's a
> stack at all

Wrong (to the degree that nonsense can be said to be wrong, but it might
more correct to say that it's not even wrong).

Possibly you mean that they don't specify the stack implementation,
whether it's a linked list or an ordinary machine stack or what.

But both languages support recursive function calls with automatic local
variables: in the general case this is impossible without a stack.

> how could be there a requirement on how things have to be organized
> on the stack?

There is the general stack requirement, last-in-first-out, which is the
definition of a stack.

However. this applies, as a logical necessity, to allocations of
function call frames, not to allocations of individual local variables.

I suspect the OP mistakenly thought the stack behavior for allocation
was required for individual automatic storage local variables, since
their constructor and destructor calls are in LIFO order.


Cheers & hth.,

- Alf

[Kalle Olavi Niemitalo]

Bob Langelaan <bobl...@gmail.com> writes:

> Any idea as to why it appears that the double ** variable is
> put on stack before the double * variable ?

If the variables are not part of the same object, then the
language doesn't specify where they are located in memory
relative to each other.
(IIRC, built-in pointer comparisons like &a < &b are undefined
in such cases, but std::less<void*>()(&a, &b) is fine.)
You can do the following though,

int main()
{
struct {
double myArray[10];
double * dblePtr;
double ** dblePtrToPtr;
} vars;
// then use vars.myArray, etc.
}

and the addresses will then stay in declaration order.
(If not all data members were public, then the order
might be different.)

[Bob Langelaan]

On Saturday, April 16, 2016 at 4:38:24 PM UTC-7, Alf P. Steinbach wrote:
> On 17.04.2016 01:05, Jens Thoms Toerring wrote:

Thank you to all the people who have replied.

I would like to ask a question in regards to the last paragraph that Alf posted. If I interpret it correctly, that even though "constructor and destructor calls are in LIFO order", I should not assume that the automatic local variables are in fact stored on some form of a stack? If this is the case, it seems to me that any other form of data structure would be awkward to use/implement and still have the LIFO order maintained.

Thanks again :)

[Ben Bacarisse]

Bob Langelaan <bobl...@gmail.com> writes:

> On Saturday, April 16, 2016 at 4:38:24 PM UTC-7, Alf P. Steinbach wrote:
>> On 17.04.2016 01:05, Jens Thoms Toerring wrote:

<snip>

>> > Actually, neither the C nor C++ standard even mandate that there's a
>> > stack at all
>>
>> Wrong (to the degree that nonsense can be said to be wrong, but it might
>> more correct to say that it's not even wrong).
>>
>> Possibly you mean that they don't specify the stack implementation,
>> whether it's a linked list or an ordinary machine stack or what.
>>
>> But both languages support recursive function calls with automatic local
>> variables: in the general case this is impossible without a stack.
>>
>>
>> > how could be there a requirement on how things have to be organized
>> > on the stack?
>>
>> There is the general stack requirement, last-in-first-out, which is the
>> definition of a stack.
>>
>> However. this applies, as a logical necessity, to allocations of
>> function call frames, not to allocations of individual local variables.
>>
>> I suspect the OP mistakenly thought the stack behavior for allocation
>> was required for individual automatic storage local variables, since
>> their constructor and destructor calls are in LIFO order.

<snip>

> Thank you to all the people who have replied.
>
> I would like to ask a question in regards to the last paragraph that
> Alf posted. If I interpret it correctly, that even though "constructor
> and destructor calls are in LIFO order", I should not assume that the
> automatic local variables are in fact stored on some form of a stack?

There's a lot of confusion here. Alf is not saying that. In fact he's
saying that automatic local variables will be on a stack. His point is
that just because this might be the case, it is not the mechanism by
with constructor and destructor calls are maintained. Within a function
the local object can be positioned as the compiler likes, provided the
constructors and destructors are called correctly.

But (and this is an aside) there is no guarantee that anything will be
stored in a stack-like structure. In the general case you do need a
LIFO structure for function calls, but if the functions are not
(mutually) recursive, only the return addresses need to be stored in a
stack like structure -- function locals could be in statically allocated
storage. And if, like in your example, there is only one function, you
don't need even that small stack-like structure.

Now, from a practical point of view, there is no reason for a compiler
to abandon what it must do in the general case (fully mutually recursive
function calls) and do something special when it detects that it could,
so stack allocation is to be expected, but it's not guaranteed by the
language.

> If this is the case, it seems to me that any other form of data
> structure would be awkward to use/implement and still have the LIFO
> order maintained.

When the compiler inlines a function call, one of the things it is doing
is optimising away a stack frame, but any automatic objects in the
function body must still behave correctly with the constructors and
destructors called in the right order. This is not very different to
what happens when entering a block with declared objects.

Remember that construction is really initialisation. The compiler will
often allocate one area for an object and then call the constructor many
times to simulate objects coming and going:

void f()
{
...
while (...) {
A a(42);
B b(43);
...
}
...
}

might compile to

void f()
{
space big enough for b;
space big enough for a;
...
while (...) {
call A's constructor(&a, 42);
call B's constructor(&b, 43);
...
call B's destructor;
call A's destructor;
}
...
}

Here the constructor/destructor order is maintained with no relation to
stack pushing and popping or relative addresses.

--
Ben.

[Bob Langelaan]

On Saturday, April 16, 2016 at 6:36:11 PM UTC-7, Ben Bacarisse wrote:

Thanks Ben. Very clear. You could/should be an instructor :)

Bob

[Kalle Olavi Niemitalo]

Ben Bacarisse <ben.u...@bsb.me.uk> writes:

> Now, from a practical point of view, there is no reason for a compiler
> to abandon what it must do in the general case (fully mutually recursive
> function calls) and do something special when it detects that it could,

That depends on the target CPU. The venerable Intel MCS-51
microcontrollers do not support a register+constant addressing
mode, so if the compiler places variables on the stack, it has to
emit additional instructions to compute the address of each
variable. The generated code becomes larger and slower.

I remember using a version of Keil C51 that did not support
reentrant functions and always placed local variables in
statically allocated storage. To minimize the amount of memory
needed, the linker computed a call graph and chose overlapping
locations where possible. Calls via function pointers had to be
pointed out to the linker. That compiler was for C rather than
C++ but I except a C++ compiler would have done the same thing,
and calls via virtual function tables might even be easier to
analyze than calls via program-defined function pointers.

Later versions of Keil C51 support reentrant functions too, but
the documentation advises that those are inefficient and should
be used sparingly.

http://www.keil.com/support/man/docs/c51/c51_le_reentrantfuncs.htm
http://www.keil.com/support/man/docs/lx51/lx51_in_overlaying.htm

One version I used had a surprising bug with C++-style // comments.
When I did

#define SOME_MACRO 0x28 // Decriptive comment.
int i = SOME_MACRO + 1;

the "+ 1;" part got commented out.
Those were the times.

[David Brown]

On 17/04/16 01:38, Alf P. Steinbach wrote:
> On 17.04.2016 01:05, Jens Thoms Toerring wrote:
>> qBob Langelaan <bobl...@gmail.com> wrote:
>>> Can I assume if instead of defining pointers we were defining
>>> objects with associated dtors, that they would always be put on the
>>> stack in the expected order to ensure that the dtors are invoked in
>>> the correct order?
>>
>> Sorry, but you can't.
>
> Right.
>
>
>> The compiler can, more ore less, put any object whereever it likes.
>
> C++ provides a guaranteed ordering for data members with the same access
> level.

This is trumped by the "as is" rule. C++ can re-order as much as it
likes, as long as it /appears/ to the code that the objects follow that
ordering. If you have objects that the standard says must be in a
certain order, but the code never takes the address of these objects,
then the compiler can put them wherever it likes (including holding them
in registers, or eliminating them altogether - as long as the program
logic is unchanged).

>
>
>> Actually, neither the C nor C++ standard even mandate that there's a
>> stack at all
>
> Wrong (to the degree that nonsense can be said to be wrong, but it might
> more correct to say that it's not even wrong).

No, he is correct - there is no requirement for a stack. C is used on
small microcontrollers that don't have any sensible support for a stack,
though it is rare to see C++ on such systems. There are odd processor
architectures with no stack, or with multiple stacks, that have at least
C compilers - and there is no fundamental reason for them not to have
C++ compilers.

Having a stack is typically the easiest way to implement the
requirements of C and C++ - but it is not the only way.

>
> Possibly you mean that they don't specify the stack implementation,
> whether it's a linked list or an ordinary machine stack or what.
>
> But both languages support recursive function calls with automatic local
> variables: in the general case this is impossible without a stack.
>

It is perfectly possible to implement recursive functions without a
stack - a linked list, as you mentioned above, is /not/ a stack. It is
perfectly legal for a compiler to analyse the source code, see that the
recursive functions in use have a maximum depth of 3, and allocate 3
sets of fixed statically allocated data space for their variables. In
the general case, a stack is far and away the easiest and most efficient
way to handle recursive functions (and many other features of C and
C++), but it is not required.

For example, on an 8051, a C compiler will usually not generate any data
stack for most programs.

>
>> how could be there a requirement on how things have to be organized
>> on the stack?
>
> There is the general stack requirement, last-in-first-out, which is the
> definition of a stack.
>
> However. this applies, as a logical necessity, to allocations of
> function call frames, not to allocations of individual local variables.
>
> I suspect the OP mistakenly thought the stack behavior for allocation
> was required for individual automatic storage local variables, since
> their constructor and destructor calls are in LIFO order.
>

Yes - position on the stack (assuming you have one) has no influence on
the logical allocation order of data, which is the important ordering
for constructor and destructor ordering.

[Alf P. Steinbach]

On 17.04.2016 13:00, David Brown wrote:
> a linked list, as you mentioned above, is /not/ a stack.

It seems there's an outbreak of nonsense today. This is the third, if
not fourth, nonsense statement I've seen today. Presumably the above
(plus the rest, but I chose this little part) seemed to make perfect
sense to you when you wrote it, and perhaps still!, so I'll spell it out
for you: you're arguing that one can't implement a stack with a linked
list, and I'm very sorry, but that's complete idiocy.

[David Brown]

You can use a linked list to implement a stack, yes. You can even do so
using a singly linked list, though it will be very inefficient.

But in the context of the low-level aspects of compiler code generation,
or of basic cpu features, "stack" has a particular meaning other than
simply "something that implements the API of a LIFO". The key features
of a stack, in this context, are a contiguous block of memory and a
"stack pointer" that indicates the current depth of the stack.
Additional features may include limit markers, access protection, etc.
Granted, this is a particular way of implementing a more general stack -
but it is this single particular implementation that is meant here.

[Vir Campestris]

Having read right the way up to 2109 today...

AIUI (and there are people here who are able to correct me if I am
wrong) the compiler's quite entitled to stick some/all of those
variables in registers - in which case they don't really have an
address, and certainly aren't on a stack. So by asking for an address
you're actually constraining the compiler's optimisation.

Andy

[Alf P. Steinbach]

On 17.04.2016 22:09, David Brown wrote:
> On 17/04/16 21:24, Alf P. Steinbach wrote:
>> On 17.04.2016 13:00, David Brown wrote:
>>> a linked list, as you mentioned above, is /not/ a stack.
>>
>> It seems there's an outbreak of nonsense today. This is the third, if
>> not fourth, nonsense statement I've seen today. Presumably the above
>> (plus the rest, but I chose this little part) seemed to make perfect
>> sense to you when you wrote it, and perhaps still!, so I'll spell it out
>> for you: you're arguing that one can't implement a stack with a linked
>> list, and I'm very sorry, but that's complete idiocy.
>>
>
> You can use a linked list to implement a stack, yes.

Right.

> You can even do so
> using a singly linked list, though it will be very inefficient.

I'm sorry, that's more nonsense.

There is an [1]inefficiency of dynamic allocation of different size
chunks, forced by different size stack frames.

But that has nothing to do with [2]singly linked versus double or
multiply linked.

> But in the context of the low-level aspects of compiler code generation,
> or of basic cpu features, "stack" has a particular meaning other than
> simply "something that implements the API of a LIFO".

Generally right, but

• in the context of Norwegian, which is also irrelevant, “stakk” is an
old word that means a skirt;

• in the context of restaurant kitchens, …

Cheers & hth.,

- Alf

Notes:

[1] That is, inefficiency compared to an array implementation where an
array implementation is applicable. Which currently is most common. An
example where an array implementation of the C/C++ stack probably won't
do, is a (sufficiently) large number of co-routines or threads where at
least some of them use general recursion. Then a linked implementation
can conceivably and probably be more efficient.

[2] Indeed, contrary to your statement, since double linking requires
twice the number of link updates, and M times the overhead for M links
per node, the singly linked list is /slightly more efficient/. However,
even though that fact has rhetorical value, the link maintenance
overhead is peanuts compared to the dynamic allocation overhead. The
mention of singly linked is simply not meaningful.

[Jerry Stuckle]

If what you say is true, then you couldn't run C on IBM mainframes -
which have no hardware stack or assembler instructions which support a
stack.

On these systems, automatic allocation is implemented with a linked
list. There is no "stack pointer that indicates the current depth of
the stack".

But obviously you CAN run C programs (and even Linux) on these machines.

--
==================
Remove the "x" from my email address
Jerry Stuckle
jstu...@attglobal.net
==================

[Robert Wessel]

On Sun, 17 Apr 2016 22:09:06 +0200, David Brown
<david...@hesbynett.no> wrote:

>On 17/04/16 21:24, Alf P. Steinbach wrote:
>> On 17.04.2016 13:00, David Brown wrote:
>>> a linked list, as you mentioned above, is /not/ a stack.
>>
>> It seems there's an outbreak of nonsense today. This is the third, if
>> not fourth, nonsense statement I've seen today. Presumably the above
>> (plus the rest, but I chose this little part) seemed to make perfect
>> sense to you when you wrote it, and perhaps still!, so I'll spell it out
>> for you: you're arguing that one can't implement a stack with a linked
>> list, and I'm very sorry, but that's complete idiocy.
>>
>
>You can use a linked list to implement a stack, yes. You can even do so
>using a singly linked list, though it will be very inefficient.

Why? Assuming the usual usage pattern for a stack (where you can add
or remove things only from the top, and possible peek a few items down
from the top), why would you need more than a singly-linked list,
starting from the topmost element?

>But in the context of the low-level aspects of compiler code generation,
>or of basic cpu features, "stack" has a particular meaning other than
>simply "something that implements the API of a LIFO". The key features
>of a stack, in this context, are a contiguous block of memory and a
>"stack pointer" that indicates the current depth of the stack.
>Additional features may include limit markers, access protection, etc.
>Granted, this is a particular way of implementing a more general stack -
>but it is this single particular implementation that is meant here.

The word means both things. The C standard clearly specifies certain
behaviors that require a stack in the general LIFO sense. On some
implementations that's implemented on the traditional (x86-like)
hardware stack. The former is required for a full implementation of
C, at least for some programs, the latter is an implementation detail
(and *not* a universal one*). Failing to distinguish between the two
leads to long and silly Usenet debates.


*There have been implementations that use a linked-list-based stack
(some S/360 family implementations, for example), and implementations
that use multiple parallel stacks (SPARC and IPF, for example) to
implement the one "stack" required by the C standard.

[Robert Wessel]

Sometimes, sometimes not. Most of the C compilers for mainframes will
use a more contiguous stack for much of the code, and use the S/360
traditional linked-list (R13-based) mechanism only for functions that
call or are called from outside. Forcing the traditional (and quite
slow) mechanism for the very many calls to very short routines common
in C would be very painful. Obviously there are no "real" stack
manipulation instructions (discounting the unrelated stacking Program
Call instructions), but adding and subtracting to/from a register is
hardly a big deal. But yes, most C code being executed on S/360
family machines uses a stack structure very similar to that used by
typical x86 implementations. As do many of the implementations on
RISCs that also lack hardware stacks.

[Jens Thoms Toerring]

Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
> On 17.04.2016 22:09, David Brown wrote:
> > But in the context of the low-level aspects of compiler code generation,
> > or of basic cpu features, "stack" has a particular meaning other than
> > simply "something that implements the API of a LIFO".

> Generally right, but

> • in the context of Norwegian, which is also irrelevant, “stakk” is an
> old word that means a skirt;

> • in the context of restaurant kitchens, …

What's bitten you? The OP mentioned "stack" and it was clear (at
least to me) from the context that he didn't mean some abstract
implementation of a LIFO but the "stack" that most people with
some knowledge about common hardware know about (and some assume
to be the only way it can be done), i.e. the one that is made up
of (at least) a piece of memory and a stack pointer.

All I tried to express was that such a "stack" isn't something
that's prescribed by the standard and that it's thus not rea-
sonable to expect some order of creation of local variables in
memory that would only make sense (if it were mandated) if such
a "stack" were required.

[Jens Thoms Toerring]

Jens Thoms Toerring <j...@toerring.de> wrote:
> Bob Langelaan <bobl...@gmail.com> wrote:
> > This output below is produced using MS VS 2105 in Release mode.

> > Any idea as to why it appears that the double ** variable is put on stack
> >before the double * variable ?

> > #include <iostream>
> > using namespace std;

> > int main()
> > {
> > double myArray[10]; // define an array of 10 doubles
> > cout << "Address of myArray is: " << myArray;

> > double * dblePtr; // define a pointer to double
> > double ** dblePtrToPtr; // define a pointer to a pointer of type double

> > cout << "\n\nAddress of dblePtr is: " << &dblePtr;
> > cout << "\n\nAddress of dblePtrToPtr is: " << &dblePtrToPtr;

> > cout << "\n\nSize of dblePtr: " << sizeof dblePtr;
> >
> > cout << endl;
> > return 0;

> > }

> > OUTPUT:
> > Address of myArray is: 0033FE10
> > Address of dblePtr is: 0033FE08
> > Address of dblePtrToPtr is: 0033FE0C

Another point: stacks can grow either from lower to higher addres-
ses or the other way round. What would be the "expected ordering"
if the stack grows from high to low addresses? If the compiler
first "sees" variables 'A' and makes room for it on the stack and
then sees 'B' and does it again, on a system where the stack grows
from lower to higher addresses 'A' might appear at a lower address
than 'B', but on a system where the stack grows in the other direc-
tion it might be just the other way round. That's another reason
why there can't be an "expected order".

[Alf P. Steinbach]

On 18.04.2016 00:28, Jens Thoms Toerring wrote:
> Alf P. Steinbach <alf.p.stein...@gmail.com> wrote:
>> On 17.04.2016 22:09, David Brown wrote:
>>> But in the context of the low-level aspects of compiler code generation,
>>> or of basic cpu features, "stack" has a particular meaning other than
>>> simply "something that implements the API of a LIFO".
>
>> Generally right, but
>
>> • in the context of Norwegian, which is also irrelevant, “stakk” is an
>> old word that means a skirt;
>
>> • in the context of restaurant kitchens, …
>
> What's bitten you?

Multiple people independently silly-asserting that C++ doesn't require a
stack, on the same day.

I think Fortran 77 didn't require a stack.

Also, as I recall Knuth's MIX assembly language didn't require a stack.
I liked the way he passed return addresses by modifying the code of the
called function. Also it had the nice property that you couldn't really
tell whether the hardware used binary or decimal. Very good for an
assembly language targeting 1950's computers. And Knuth did much of this
while he was a postdoc, I think it was, at Norsk Regnesentral, which is
also the environment that produced the Simula language and object
orientation, on which the C++ object orientation is based (and also OO
in other language, mostly via Smalltalk, I think: Alan Key, of Smalltalk
fame, got a tape with a compiler that he thought was Algol, and hey, it
was Simula! – and the rest, as they say, is history).

> The OP mentioned "stack" and it was clear (at
> least to me) from the context that he didn't mean some abstract
> implementation of a LIFO but the "stack" that most people with
> some knowledge about common hardware know about (and some assume
> to be the only way it can be done), i.e. the one that is made up
> of (at least) a piece of memory and a stack pointer.

Yes, I thought as much, hence my speculation in my reply, that that was
what you meant.

I think we can use the descriptive term “contiguous stack area” for this.

And then we can say that neither C nor C++ require a contiguous stack area.


Cheers!,

- Alf

[Jerry Stuckle]

I didn't say the compiler had to generate storage requests to the OS.
It can easily do the same by subdividing an existing storage. It could
easily use linked lists for this. When I worked for IBM, we did a lot
of assembler this way, including recursive routines. And we almost
never had to request more storage from the OS.

And no, the R13 linked list format is *not* just used for functions that
call or are called from the outside. It is used quite extensively with
internal calls also - including setting up the above pseudo-stack.

But either way, there is no hardware stack. I will agree it is an
emulation. But C does not require a stack. Only a way to create a
unique storage area when a function is called.

[Alf P. Steinbach]

On 18.04.2016 03:59, Jerry Stuckle wrote:
>
> But C does not require a stack. Only a way to create a
> unique storage area when a function is called.

That is a stack.

Similarly one can argue that people do not need air, only a way to keep
the blood oxygenated, and /that/ only as long as the person is alive.


Cheers & hth.,

- Alf (nonsense-fighter for the occasion)

[Jerry Stuckle]

It is not a stack in the hardware sense. It is the emulation of a
stack. There is no stack pointer register to increment/decrement as
necessary, no push/pop instructions, not even call/return instructions.
IOW, nothing that people normally associate with a stack. It is simply
a linked list, entirely handled by software.

Assume you have three horses and two cows. You tell people the cows are
horses. How many horses do you have? The answer is still three.
Calling a cow a horse does not make it a horse.

[Alf P. Steinbach]

On 18.04.2016 04:24, Jerry Stuckle wrote:
> On 4/17/2016 10:12 PM, Alf P. Steinbach wrote:
>> On 18.04.2016 03:59, Jerry Stuckle wrote:
>>>
>>> But C does not require a stack. Only a way to create a
>>> unique storage area when a function is called.
>>
>> That is a stack.
>>
>> Similarly one can argue that people do not need air, only a way to keep
>> the blood oxygenated, and /that/ only as long as the person is alive.
>>
>>
>> Cheers & hth.,
>>
>> - Alf (nonsense-fighter for the occasion)
>>
>
> It is not a stack in the hardware sense. It is the emulation of a
> stack. There is no stack pointer register to increment/decrement as
> necessary, no push/pop instructions, not even call/return instructions.
> IOW, nothing that people normally associate with a stack. It is simply
> a linked list, entirely handled by software.
>
> Assume you have three horses and two cows. You tell people the cows are
> horses. How many horses do you have? The answer is still three.
> Calling a cow a horse does not make it a horse.

I hope you'll realize, sooner or later, that in C++ we still have STACK
UNWINDING of this list that in your opinion isn't a stack.


Cheers!,

- Alf (still fighting nonsense)

[David Brown]

We can certainly agree that neither C nor C++ needs a "contiguous stack
area" (though the great majority of modern practical implementations
/do/ have such a stack). And we can certainly agree that in order to
implement recursive functions, some sort of LIFO structure is necessary.

(In compilers for microcontrollers with poor support for a "contiguous
stack area", such as the 8051, recursive or re-entrant functions are
strongly discouraged because they force the compiler to create a stack
which is otherwise avoided.)

All we disagree on, as far as I can tell, is what the unqualified term
"stack" means in this discussion. And since it is clear what /you/ mean
by "stack", and clear what /I/ (and a few others here) mean, we can
probably leave that part of the discussion there without any need to
tell people they are talking nonsense for using terms others feel are
well understood within the context.


The real point of interest for the OP to learn here, is that while the
compiler might put data on a physical stack (of any sort) for
convenience and efficiency, it is not actually fundamental to the
language, and the ordering of data on the physical stack is not
fundamental. It does not relate directly to the order of creation or
destruction of the objects.

C++ (but not C) has a /logical/ stack holding objects with automatic
storage duration in declared order - when an exception is thrown, these
are destroyed in reverse order by "stack unwinding". But the order on
this virtual or logical stack does not need to match that of any
physical stack - data can be in registers, at fixed addresses, or held
in any other way as long as the compiler has enough information to do
"stack unwinding". As far as I can tell, the C++ standards only refer
to the term "stack" for "stack unwinding" on exceptions, and as a type
of standard container.

[David Brown]

What I said was that you /could/ use a linked list (or some other
structure) in order to implement the LIFO needed for recursive functions
in C - but that it is a good deal less efficient than using a simple
contiguous stack block and stack pointer.

I don't know anything much about the processors used on IBM mainframes,
until the Power architecture was used. Certainly on a Power cpu, there
is no problem using a contiguous stack block (they have addressing modes
to efficiently implement code such as "x = *sp++; *sp-- = y; z =
sp[4]"). These processors don't have a dedicated stack pointer register
- you can use (almost) any general purpose register you like as a stack
pointer, and can have as many stacks as you want. While I haven't used
a Power cpu myself, I have used PowerPC processors which have most of
the basic ISA in common - and C compilers for PPC work in the
traditional manner with contiguous stacks. Of course, there could be
other reasons for IBM mainframes not using such "normal" stacks - I
don't know enough about them to say.

[Öö Tiib]

C++ standard does not discuss call stack. Instead there are life-times,
storages and scopes. Destroying objects in reverse order to construction
when life-time of objects ends is called "stack unwinding". You are correct
that some sort of LIFO has to be there for implementing that. OP did
however hack with execution stack of thread and that is entirely left to be
as internals of implementation.

[Jerry Stuckle]

So now you have to resort to personal attacks to get your point across?
It must not be a very strong argument.

Neither the C or C++ standards say ANYTHING about a stack. "Stack
unwinding" is a process, and processes can be implemented in a number of
ways. For instance, in a processor with no multiplication instruction,
you can still multiply by repeated additions.

A linked list is not a stack. But you can still implement a stack
unwinding process using a linked list.

[Jerry Stuckle]

It doesn't have to be "a good deal less efficient". A linked list,
properly optimized for a specific case, can be almost efficient as a
stack. And you can implement a linked list in any processor. You can't
do that with a stack.

> I don't know anything much about the processors used on IBM mainframes,
> until the Power architecture was used. Certainly on a Power cpu, there
> is no problem using a contiguous stack block (they have addressing modes
> to efficiently implement code such as "x = *sp++; *sp-- = y; z =
> sp[4]"). These processors don't have a dedicated stack pointer register
> - you can use (almost) any general purpose register you like as a stack
> pointer, and can have as many stacks as you want. While I haven't used
> a Power cpu myself, I have used PowerPC processors which have most of
> the basic ISA in common - and C compilers for PPC work in the
> traditional manner with contiguous stacks. Of course, there could be
> other reasons for IBM mainframes not using such "normal" stacks - I
> don't know enough about them to say.
>

When I worked for IBM, I did a lot of work on mainframes, both in
assembler and machine code (sometimes we had to write patches for
customers who didn't have the source code).

Sure, you can emulate a stack on IBM mainframes using registers. But it
is much easier to do so with linked lists. But the PowerPC is not the
same as the IBM mainframes; they are entirely different architectures
with entirely different instruction sets.

[red floyd]

On 4/16/2016 6:33 PM, Ben Bacarisse wrote:

> But (and this is an aside) there is no guarantee that anything will be
> stored in a stack-like structure. In the general case you do need a
> LIFO structure for function calls, but if the functions are not
> (mutually) recursive, only the return addresses need to be stored in a
> stack like structure -- function locals could be in statically allocated
> storage. And if, like in your example, there is only one function, you
> don't need even that small stack-like structure.
>

In fact, I once created a compiler (for a very limited simulated
machine) that supported recursion by copying static data onto the
stack, and then using static locations for local variables. Thus
each instance of the recursive function had the same addresses for
its variables (please note, the toy language had no operators for
dealing with pointers or addresses).

[Gareth Owen]

Jerry Stuckle <jstu...@attglobal.net> writes:

> So now you have to resort to personal attacks to get your point across?
> It must not be a very strong argument.

Oh Bravo, Jerry!

[David Brown]

How do you have a processor that can efficiently implement a linked
list, but cannot reasonably implement a plain stack? I am not denying
that this is the case for the IBM mainframes you refer to - you have
worked with them, and I have not. I am just curious what the cpu ISA
looks like.

For small microcontroller devices like the 8051, the COP8, PIC12, etc.,
a data stack is very inefficient. But a linked list would be even
worse. These devices do not have good pointer registers or pointer
access modes. To implement a basic stack operation such as "x = *sp++"
you must perhaps do roughly:

ld a, sp // sp is a variable in memory
mv iLo, a // iLo + iHi are special memory-mapped registers
ld a, sp+1
mv iHi, a
ld a, indirect // memory-mapped register for mem[iHi:iLo]
st a, x // x is variable in memory
ld a, sp
add a, #1
st a, sp
ld a, sp+1
adc a, #0
st a, sp+1

You /can/ implement a stack, or a linked list, but with such a
restricted instruction set and limited addressing modes, it is clearly
going to be very inefficient.

But I don't see how you could have an ISA that has reasonable registers,
instructions, and addressing modes for working with linked lists, and
not also be able to use these for accessing a stack.

>
>> I don't know anything much about the processors used on IBM mainframes,
>> until the Power architecture was used. Certainly on a Power cpu, there
>> is no problem using a contiguous stack block (they have addressing modes
>> to efficiently implement code such as "x = *sp++; *sp-- = y; z =
>> sp[4]"). These processors don't have a dedicated stack pointer register
>> - you can use (almost) any general purpose register you like as a stack
>> pointer, and can have as many stacks as you want. While I haven't used
>> a Power cpu myself, I have used PowerPC processors which have most of
>> the basic ISA in common - and C compilers for PPC work in the
>> traditional manner with contiguous stacks. Of course, there could be
>> other reasons for IBM mainframes not using such "normal" stacks - I
>> don't know enough about them to say.
>>
>
> When I worked for IBM, I did a lot of work on mainframes, both in
> assembler and machine code (sometimes we had to write patches for
> customers who didn't have the source code).
>
> Sure, you can emulate a stack on IBM mainframes using registers. But it
> is much easier to do so with linked lists. But the PowerPC is not the
> same as the IBM mainframes; they are entirely different architectures
> with entirely different instruction sets.
>

OK. As I said, I am not familiar with the cpus IBM use in their big
systems, other than the Power processors.

[Vir Campestris]

On 18/04/2016 00:54, Alf P. Steinbach wrote:
> I think Fortran 77 didn't require a stack.

I'm older than that ;)

I recall proving to myself that Fortran IV on a DECSystem10 didn't have
a stack. Function A wasn't allowed to call itself, but it could call B
which called A. Except you then found out they were using the same local
variables, as if they were all what I now call static. Didn't learn C
until many years later.

Andy

[Vir Campestris]

On 18/04/2016 03:12, Alf P. Steinbach wrote:
> On 18.04.2016 03:59, Jerry Stuckle wrote:
>>
>> But C does not require a stack. Only a way to create a
>> unique storage area when a function is called.
>
> That is a stack.

Well, that could equally well be a heap. Which is of course a great
place to put a linked list...

For the OP's sake I think BTW it's worth pointing out that the direction
the stack grows can be towards high, or towards low, addresses on
different architectures. Some can go either way, and I've met some that
will allow you to have multiple stacks going in different directions.

Multiple stacks BTW can be handy if you're writing an interpreter - you
can keep one for the interpreted program's data, and one for the
interpreter.

Andy

[Scott Lurndal]

David Brown <david...@hesbynett.no> writes:
>On 18/04/16 18:26, Jerry Stuckle wrote:

>How do you have a processor that can efficiently implement a linked
>list, but cannot reasonably implement a plain stack? I am not denying
>that this is the case for the IBM mainframes you refer to - you have
>worked with them, and I have not. I am just curious what the cpu ISA
>looks like.

Burroughs B4800. Three (later gens had 7) index registers make linked lists
easy (there are even instructions that will search a linked list
for one of 9 different conditions with a variable length key at a
variable offset from the start of the list element).

http://vseries.lurndal.org/doku.php?id=instructions:slt

There is no SP. For the call stack, the processor will read the
6 digit value from address 40 relative to base register 0 and
use that as the address in memory for the stack (also relative to
base 0), and will update it as data is pushed on the stack.

There are -zero- general purpose registers. Everything except
the three (or 7) index registers (which are used for addressing)
is memory-to-memory including all the arithmetic instructions
(except for floating point which uses a single accumulator).

>But I don't see how you could have an ISA that has reasonable registers,
>instructions, and addressing modes for working with linked lists, and
>not also be able to use these for accessing a stack.

Registers? Who needs them :-).

[Alf P. Steinbach]

On 18.04.2016 22:07, Vir Campestris wrote:
> On 18/04/2016 03:12, Alf P. Steinbach wrote:
>> On 18.04.2016 03:59, Jerry Stuckle wrote:
>>>
>>> But C does not require a stack. Only a way to create a
>>> unique storage area when a function is called.
>>
>> That is a stack.
>
> Well, that could equally well be a heap.

No, a heap doesn't have LIFO behavior. The LIFO behavior for the
allocations and deallocations is forced by the languages' support for
general recursion, which can generate arbitrary long chains of stack
frames for the call stack. The C++ standard refers to it as a stack, and
we use terms such as “stack frame” and “call stack”, because it's a
stack, regardless of the implementation details.


Cheers & hth.,

- Alf (nonsense fighter)

[Robert Wessel]

On Sun, 17 Apr 2016 21:59:59 -0400, Jerry Stuckle

I didn't say it either.

>It can easily do the same by subdividing an existing storage. It could
>easily use linked lists for this. When I worked for IBM, we did a lot
>of assembler this way, including recursive routines. And we almost
>never had to request more storage from the OS.
>
>And no, the R13 linked list format is *not* just used for functions that
>call or are called from the outside. It is used quite extensively with
>internal calls also - including setting up the above pseudo-stack.

In the context of C or C++ programs, the traditional S/360 method is
not used for most internal calls. You generally need to specify
traditional linkage explicitly (via either #pragma linkage or a
specification on the extern statement) on those functions where it's
needed. At least for normal C/C++ since the later OS/390 days. The
(normally used) XPLink convention uses R4 to address a typical
"hardware-style" stack, and reserves various registers for passing
parameters and return values.

MetalC is different, and does use the R13-based linked list by
default.

>But either way, there is no hardware stack. I will agree it is an
>emulation. But C does not require a stack. Only a way to create a
>unique storage area when a function is called.

C does not require a hardware-style stack. It does, for at least some
programs, require a stack in the general CS sense.

[Robert Wessel]

On Mon, 18 Apr 2016 21:40:56 +0200, David Brown
<david...@hesbynett.no> wrote:

>> When I worked for IBM, I did a lot of work on mainframes, both in
>> assembler and machine code (sometimes we had to write patches for
>> customers who didn't have the source code).
>>
>> Sure, you can emulate a stack on IBM mainframes using registers. But it
>> is much easier to do so with linked lists. But the PowerPC is not the
>> same as the IBM mainframes; they are entirely different architectures
>> with entirely different instruction sets.
>>
>
>OK. As I said, I am not familiar with the cpus IBM use in their big
>systems, other than the Power processors.

Creating a "hardware-style" stack using a register as a base is as
straight-forward on Z as you'd expect (and as is done by the C
compiler by default), and using a linked-list is not "easier" (except
in the sense that the linked-list approach is the system calling
convention, so if you interface to other things you will need to use
the old calling convention).

[David Brown]

On 18/04/16 22:20, Scott Lurndal wrote:
> David Brown <david...@hesbynett.no> writes:
>> On 18/04/16 18:26, Jerry Stuckle wrote:
>
>> How do you have a processor that can efficiently implement a linked
>> list, but cannot reasonably implement a plain stack? I am not denying
>> that this is the case for the IBM mainframes you refer to - you have
>> worked with them, and I have not. I am just curious what the cpu ISA
>> looks like.
>
> Burroughs B4800. Three (later gens had 7) index registers make linked lists
> easy (there are even instructions that will search a linked list
> for one of 9 different conditions with a variable length key at a
> variable offset from the start of the list element).
>
> http://vseries.lurndal.org/doku.php?id=instructions:slt
>
> There is no SP. For the call stack, the processor will read the
> 6 digit value from address 40 relative to base register 0 and
> use that as the address in memory for the stack (also relative to
> base 0), and will update it as data is pushed on the stack.

From your wiki (I read a little, but not all), it looks like there is a
call stack for holding return addresses and some registers, but you
don't have direct access to it for use as a data stack. Is that right?
But surely you could have a data stack if you wanted - use one of the
index registers as your data stack pointer, pointing to a block of
contiguous memory.

>
> There are -zero- general purpose registers. Everything except
> the three (or 7) index registers (which are used for addressing)
> is memory-to-memory including all the arithmetic instructions
> (except for floating point which uses a single accumulator).
>
>> But I don't see how you could have an ISA that has reasonable registers,
>> instructions, and addressing modes for working with linked lists, and
>> not also be able to use these for accessing a stack.
>
> Registers? Who needs them :-).
>

The MAXQ architecture has no registers as such - everything is memory
mapped. And it has only one instruction - "move". All ALU operations,
branches, etc., are handled by reading and writing to memory mapped
addresses:

<https://www.maximintegrated.com/en/app-notes/index.mvp/id/3222>

(I haven't programmed one of these, but we considered one of those
microcontrollers for a project a good many years ago.)


I have also programmed on a device which had 32 registers - but no ram!

[Alf P. Steinbach]

On 19.04.2016 09:27, David Brown wrote:
> On 18/04/16 22:20, Scott Lurndal wrote:
>>
>> There are -zero- general purpose registers. Everything except
>> the three (or 7) index registers (which are used for addressing)
>> is memory-to-memory including all the arithmetic instructions
>> (except for floating point which uses a single accumulator).
>>
>>> But I don't see how you could have an ISA that has reasonable registers,
>>> instructions, and addressing modes for working with linked lists, and
>>> not also be able to use these for accessing a stack.
>>
>> Registers? Who needs them :-).
>>
>
> The MAXQ architecture has no registers as such - everything is memory
> mapped. And it has only one instruction - "move". All ALU operations,
> branches, etc., are handled by reading and writing to memory mapped
> addresses:
>

As I recall the PDP-11 also had memory mapped registers.

However, at the time, I was in college, all I did of programming with
the PDP-11 was “Hello, world!” in assembly. This was due to all
information about how to use the machines being channeled through
classroom lectures, and to me the lectures were excruciatingly boring
and slooooow, a kind of psychological terror warfare. Well OK, I also
used PDP-11 machines to test an NC “direct connection” single board
computer that another student and I developed in MP/L-86, and moved the
disks of one PDP-11 machine from the college to the machine hall of
Kongsberg Våpenfabrikk, and it worked just fine there (I was not sure
whether that would work). So it's weird. I was surrounded by PDP-11
machines and used them for some tasks, but I failed to see how elegant
they were on the inside. Possibly put off by PIP and STAT commands. :(


Cheers!,

- Alf

[David Brown]

I don't know much about the PDP-11 itself, but the TI msp430
microcontroller cpu ISA is heavily based on that of the PDP-11. The cpu
registers are not memory mapped, but hardware registers and I/O
registers are memory mapped. At the time of the PDP-11, I believe it
was standard practice for I/O access to be separate from memory access,
using different instructions (you still get this on some processors and
microcontrollers) - the PDP-11 was unusual in that I/O access was done
using the same instructions and address space as RAM access. (The
msp430 is a very nice ISA - I have enjoyed working with it in both
assembly and C.)

You will be familiar with the AVR architecture, I hope? It has 32 8-bit
registers, which are also available in the memory map.

[Alf P. Steinbach]

On 19.04.2016 12:27, David Brown wrote:
>
> You will be familiar with the AVR architecture, I hope? It has 32 8-bit
> registers, which are also available in the memory map.

Oh this is very off-topic, but sorry, no, I'm not familiar with the AVR
architecture (I just googled it). AFAIK I never programmed a Harvard
architecture machine. But I note that one of the designers was named
Alf, which surely is a good sign, and that judging by the names, Alf
Egil Bogen and Vegard Wollan, they both appear to be Norwegians. :)

But re separation of i/o instructions, just a historical silly-fact:

the Intel 8086 was designed with two co-processors, namely the 8087 math
coprocessor, and the 8089 i/o coprocessor! I think it must have been a
design IBM lifted from their mainframes. But I've never heard of the
8089 being used in any real machine, and don't even know if it was ever
actually produced. There must be a name for that kind of technology. An
apparent big advance, which turns out to be nothing?


Cheers!,

- Alf

[David Brown]

On 19/04/16 14:45, Alf P. Steinbach wrote:
> On 19.04.2016 12:27, David Brown wrote:
>>
>> You will be familiar with the AVR architecture, I hope? It has 32 8-bit
>> registers, which are also available in the memory map.
>
> Oh this is very off-topic, but sorry, no, I'm not familiar with the AVR
> architecture (I just googled it). AFAIK I never programmed a Harvard
> architecture machine. But I note that one of the designers was named
> Alf, which surely is a good sign, and that judging by the names, Alf
> Egil Bogen and Vegard Wollan, they both appear to be Norwegians. :)
>

Exactly - the AVR was designed by Atmel in Trondheim. It is one of the
most popular 8-bit microcontroller architectures, with a wide variety of
devices. The main development of the microcontroller and tools is in
Trondheim, though some peripherals are designed elsewhere. So as a true
Norwegian patriot, you need to know about this architecture!

Actually, it is somewhat relevant for this subthread, since the AVR has
no [SP + offset] addressing mode, making stacked data inconvenient to
access. In some AVR compilers, there is a separate data stack using the
Y index register (which has [Y + offset] addressing modes) independent
of the call-return stack.

And yes, it is Harvard architecture - the code/flash address space is
separate from the data/I/O address space, which is a source of great
irritation to C and C++ programmers.

[Scott Lurndal]

David Brown <david...@hesbynett.no> writes:
>On 18/04/16 22:20, Scott Lurndal wrote:
>> David Brown <david...@hesbynett.no> writes:
>>> On 18/04/16 18:26, Jerry Stuckle wrote:
>>
>>> How do you have a processor that can efficiently implement a linked
>>> list, but cannot reasonably implement a plain stack? I am not denying
>>> that this is the case for the IBM mainframes you refer to - you have
>>> worked with them, and I have not. I am just curious what the cpu ISA
>>> looks like.
>>
>> Burroughs B4800. Three (later gens had 7) index registers make linked lists
>> easy (there are even instructions that will search a linked list
>> for one of 9 different conditions with a variable length key at a
>> variable offset from the start of the list element).
>>
>> http://vseries.lurndal.org/doku.php?id=instructions:slt
>>
>> There is no SP. For the call stack, the processor will read the
>> 6 digit value from address 40 relative to base register 0 and
>> use that as the address in memory for the stack (also relative to
>> base 0), and will update it as data is pushed on the stack.
>
>From your wiki (I read a little, but not all), it looks like there is a
>call stack for holding return addresses and some registers, but you
>don't have direct access to it for use as a data stack. Is that right?

Correct, although IX3 (index register 3) by convention holds the
"frame pointer" for the current frame. It's automatically adjusted
by VEN/RET (and the older NTR/EXT). The ASP instruction will adjust
the TOS value at BASE.+40.6.UN based on the literal value in the A
syllable of the instruction to provide space for local storage
(and the GENERATE intrinsic in the SPRITE language which is similar to alloca()
from BSD).

Local variables will be indexed via IX3.

IX1, IX2 and IX3 are in actuality located at BASE.+8.7.SN, BASE.+16.7.SN
and BASE.+24.7.SN (3 8-digit fields). Around 1982, we redesigned the
processor architecture (maintaining backward compability) to enhance
addressing (to allow a single program to use more than 500KBytes
and to support systems with more than 10,000,000 bytes of main memory).
At that time, we added four more index registers not tied to memory
(known as the mobile IX) and enhanced the ISA to accommodate them.

BASE.+24.7.SN indicates a data item at an offset of 24 digits
from the base of the memory area which is is a 7-digit signed
numeric field (8 digits in length with the leading sign digit).

The second (following the sign) of an Index register is a base-indicant
which selects one of 8 memory areas. So BASE.+24.IX4.3.UN, if IX1 has
the value C2001000 formally describes a three digit (nibble) field starting
1024 digits into memory area two for the current task.

> But surely you could have a data stack if you wanted - use one of the
>index registers as your data stack pointer, pointing to a block of
>contiguous memory.

Right, there were no PUSH/POP type operations in the ISA, so it would
be manually crafted. Not that different from the IBM360 and successors.

On the other hand, most systems in the late 60's and early 70's had
limited memory (systems with a million bytes of memory didn't show up
until the mid 70's). Magtape (and the more expensive disk/pack) storage
was used instead. Watching a 12-unit mag-tape sort/merge was pretty
impressive, especially on the drives that could read backwards.

[Scott Lurndal]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>On 19.04.2016 09:27, David Brown wrote:

>As I recall the PDP-11 also had memory mapped registers.

You may be remembering the PDP-8, which had an accumulator and
the single-bit link register.

The PDP-11 (and the successor VAX) had regular registers
and useful addressing modes.

>they were on the inside. Possibly put off by PIP and STAT commands. :(

Should have used UnixV6 instead of RSX-11M/RSTS-E.

[Scott Lurndal]

"Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:

> There must be a name for that kind of technology. An
>apparent big advance, which turns out to be nothing?

iAPX 432.

:-)

[Alf P. Steinbach]

On 19.04.2016 16:09, Scott Lurndal wrote:
> "Alf P. Steinbach" <alf.p.stein...@gmail.com> writes:
>> On 19.04.2016 09:27, David Brown wrote:
>
>> As I recall the PDP-11 also had memory mapped registers.
>
> You may be remembering the PDP-8, which had an accumulator and
> the single-bit link register.
>
> The PDP-11 (and the successor VAX) had regular registers
> and useful addressing modes.

My photocopied PDP-11 manual is down in the bottom of some box.

And all I could find in Wikipedia was that the Program Status Word
register was memory mapped.

It would however be strange if only one single register was memory
mapped, so I googled further and found an online PDF of a manual (in
non-machine-readable form, just scans of the pages), where I found that
at [1]least the “control registers” PS, SL, PIR, PIA and PB, whatever
those acronyms stand for, were memory mapped, in the range 17 777 770
through 17 777 776. Now that's seven addresses and five registers.
Counting also the PSW (unless the names here refer to parts of it!) we
have six registers.

>> they were on the inside. Possibly put off by PIP and STAT commands. :(
>
> Should have used UnixV6 instead of RSX-11M/RSTS-E.

Yep.


Cheers!,

- Alf

Notes:
[1] <url: http://i.stack.imgur.com/oX15F.png>, emphasis added by me. I
find SO is a nice service for posting images quickly to imgur.

[Robert Wessel]

On Tue, 19 Apr 2016 12:17:55 +0200, "Alf P. Steinbach"
<alf.p.stein...@gmail.com> wrote:

>On 19.04.2016 09:27, David Brown wrote:
>> On 18/04/16 22:20, Scott Lurndal wrote:
>>>
>>> There are -zero- general purpose registers. Everything except
>>> the three (or 7) index registers (which are used for addressing)
>>> is memory-to-memory including all the arithmetic instructions
>>> (except for floating point which uses a single accumulator).
>>>
>>>> But I don't see how you could have an ISA that has reasonable registers,
>>>> instructions, and addressing modes for working with linked lists, and
>>>> not also be able to use these for accessing a stack.
>>>
>>> Registers? Who needs them :-).
>>>
>>
>> The MAXQ architecture has no registers as such - everything is memory
>> mapped. And it has only one instruction - "move". All ALU operations,
>> branches, etc., are handled by reading and writing to memory mapped
>> addresses:
>>
>
>As I recall the PDP-11 also had memory mapped registers.

IIRC, and as far as the general purpose registers are concerned...
that was true on some low-end machines, but not on the high end
machines. A number of machines had control registers for various
purposes and those were often memory mapped.

[Robert Wessel]

While Intel called what the 8089 provided an I/O channel (or rather, a
pair of them), and that's not unreasonable, they really looked nothing
at all like S/360 channels.

The 8089 was not a coprocessor like the 8087, it was basically a fully
independent processor that used the same mechanism that a multi-socket
8086 system would use to allow multiple CPUs to share the system bus.
Nor did it implement any instructions* that you could add to your 8086
program. And the 8089 wasn't really tied to the 8086 like the 8087
was).


*8089 assembler was nothing like 8086, but it was a (rather weird)
general purpose ISA, but heavily biased towards supporting the I/O
functions and the DMA hardware in the 8089. Basically you'd write a
specific program that would be stored in the 8089s address space
(which could be partially independent of the main system address
space) for the 8089 to run, and then use shared memory to set up
control blocks and messages to pass between the main 8086 CPU and the
8089 to handle work - there were also interrupts coming back fro the
8089 and a way to poke the 8089, the later usually mapped to an 8086
I/O port.

[Robert Wessel]

On Tue, 19 Apr 2016 14:07:29 GMT, sc...@slp53.sl.home (Scott Lurndal)
wrote:

>On the other hand, most systems in the late 60's and early 70's had
>limited memory (systems with a million bytes of memory didn't show up
>until the mid 70's).

There were S/360s which could be equipped with more than 1MB of memory
by the late 60s. I'm having trouble finding a good online source,
since many of these machines had their memory capacity expanded over
their lifetimes, but here's a 1968 article about a 360/91 (which had a
minimum configuration of 1MB, and shipped in 1967) with 2MB:

http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainframe_PP2091.html

IIRC, you could order model 65s, 67s, 75s and 85s (as well as the 91s)
with 1MB (and in some cases more) memory before the 1960s expired.

[Vir Campestris]

Don't know about the 8 or 11 (though if you want to know, ask on
uk.d-i-y) but I recall the PDP10. First assembler I ever learned. The
first 16 memory locations were the registers, so to copy from register
to register you just set the memory address to a low number.

I heard once that they really were registers - to do a fast strchr or
such you should copy your code into the registers and execute it there.

Incidentally you could use any of those registers except 0 for a stack -
so if you were so inclined you could have 15 stacks!

Andy

[Jens Thoms Toerring]

David Brown <david...@hesbynett.no> wrote:
> And yes, it is Harvard architecture - the code/flash address space is
> separate from the data/I/O address space, which is a source of great
> irritation to C and C++ programmers.

I've just, for the first time, started working with micrcontrollers
with a Harvard architecture (Microchip PIC24F) and was tasked with
writing a bootloader for it. So I guess I'm now aware of what Har-
vard architecture implies, but I'm not really irritated - it's
just having to use functions/special instructions for reading/
writing from/to program memory space. But that's not different
from having to use special functions for I/O ports etc. - and
in "normal", e.g. desktop applications one can't write to pro-
gram space anyway nowadays. So what would a C or C++ program-
mer be greatly irritated about? Just curious;-)

Best regards, Jens
--
\ Jens Thoms Toerring ___ j...@toerring.de
\__________________________ http://toerring.de

[David Brown]

When you only have a few occasions to access flash data, it's not bad.
But if you have a lot of flash data, it gets annoying to have to use
extra function calls all the time. It gets particularly annoying when
you are using arrays, or when if you have strings, and arrays of strings
(using function calls to find the address of the string in the array,
then another function call to get the data at that address). Much of
this depends on the details of how your particular compiler implements
flash data - some compilers have extensions that make it reasonably simple.

And if you ever need functions that might want either data in flash or
data in ram, it gets worse. Often on such devices, you will have a
"strcpy" function for ram to ram, and a "strcpy_p" (or similar name) for
copying from flash to ram.

How much of an issue it will be depends on the tasks in hand. It may
also be possible to make useful C++ classes to hide the messy details.

In contrast, on microcontrollers you usually don't have special
functions for I/O ports - they are mostly directly mapped in memory, and
you access them as volatile variables at fixed addresses (with addresses
fixed by linker scripts, assembly modules, compiler extensions, or
simply macros that cast an integer literal into a pointer with the right
volatile type and right address).

[Jerry Stuckle]

So then please tell us - how does one implement C on an IBM mainframe -
which does have a stack pointer nore does it support push, pop, call,
return, etc. instructions?

[Jerry Stuckle]

Then why would it be slow?

>
>> It can easily do the same by subdividing an existing storage. It could
>> easily use linked lists for this. When I worked for IBM, we did a lot
>> of assembler this way, including recursive routines. And we almost
>> never had to request more storage from the OS.
>>
>> And no, the R13 linked list format is *not* just used for functions that
>> call or are called from the outside. It is used quite extensively with
>> internal calls also - including setting up the above pseudo-stack.
>
>
> In the context of C or C++ programs, the traditional S/360 method is
> not used for most internal calls. You generally need to specify
> traditional linkage explicitly (via either #pragma linkage or a
> specification on the extern statement) on those functions where it's
> needed. At least for normal C/C++ since the later OS/390 days. The
> (normally used) XPLink convention uses R4 to address a typical
> "hardware-style" stack, and reserves various registers for passing
> parameters and return values.
>

That depends on which compiler you are using. There is no "standard"
(as there is in the R13 save area standard).

> MetalC is different, and does use the R13-based linked list by
> default.
>

Yes, it depends on which compiler you are using.

>
>> But either way, there is no hardware stack. I will agree it is an
>> emulation. But C does not require a stack. Only a way to create a
>> unique storage area when a function is called.
>
>
> C does not require a hardware-style stack. It does, for at least some
> programs, require a stack in the general CS sense.
>

Which could be implemented as a linked list, allocated from the heap or
any or a number of different ways.

But many people reading this newsgroup are only aware of the X86
processors, and think the X86 stack is the only type there is.

[Jerry Stuckle]

It really doesn't matter if they can implement a plain stack or not. A
linked list can easily be used (and I was using them in the 80's on IBM
mainframes). There are no push, pop, call, return, etc. instructions,
and no stack pointer register.

But if you want to get into the architecture, I suggest you do some
googling. It is readily available (and off topic here).

> For small microcontroller devices like the 8051, the COP8, PIC12, etc.,
> a data stack is very inefficient. But a linked list would be even
> worse. These devices do not have good pointer registers or pointer
> access modes. To implement a basic stack operation such as "x = *sp++"
> you must perhaps do roughly:
>
> ld a, sp // sp is a variable in memory
> mv iLo, a // iLo + iHi are special memory-mapped registers
> ld a, sp+1
> mv iHi, a
> ld a, indirect // memory-mapped register for mem[iHi:iLo]
> st a, x // x is variable in memory
> ld a, sp
> add a, #1
> st a, sp
> ld a, sp+1
> adc a, #0
> st a, sp+1
>
> You /can/ implement a stack, or a linked list, but with such a
> restricted instruction set and limited addressing modes, it is clearly
> going to be very inefficient.
>
> But I don't see how you could have an ISA that has reasonable registers,
> instructions, and addressing modes for working with linked lists, and
> not also be able to use these for accessing a stack.
>

Linked lists can be just as efficient as stacks. They don't take many
instructions. And they do have some advantages - for instance,
libraries could have their own storage area. This way the main program
only has to worry about the storage it needs - not what libraries need.
This was quite important back in the 80's when even mainframes were
limited to 16MB of storage.

>>
>>> I don't know anything much about the processors used on IBM mainframes,
>>> until the Power architecture was used. Certainly on a Power cpu, there
>>> is no problem using a contiguous stack block (they have addressing modes
>>> to efficiently implement code such as "x = *sp++; *sp-- = y; z =
>>> sp[4]"). These processors don't have a dedicated stack pointer register
>>> - you can use (almost) any general purpose register you like as a stack
>>> pointer, and can have as many stacks as you want. While I haven't used
>>> a Power cpu myself, I have used PowerPC processors which have most of
>>> the basic ISA in common - and C compilers for PPC work in the
>>> traditional manner with contiguous stacks. Of course, there could be
>>> other reasons for IBM mainframes not using such "normal" stacks - I
>>> don't know enough about them to say.
>>>
>>
>> When I worked for IBM, I did a lot of work on mainframes, both in
>> assembler and machine code (sometimes we had to write patches for
>> customers who didn't have the source code).
>>
>> Sure, you can emulate a stack on IBM mainframes using registers. But it
>> is much easier to do so with linked lists. But the PowerPC is not the
>> same as the IBM mainframes; they are entirely different architectures
>> with entirely different instruction sets.
>>
>
> OK. As I said, I am not familiar with the cpus IBM use in their big
> systems, other than the Power processors.
>

Power processors are closer to X86 systems than they are to IBM mainframes.

[Robert Wessel]

On Tue, 19 Apr 2016 19:02:12 -0400, Jerry Stuckle

The R13 calling convention has a great deal of unnecessary overhead,
even if you don't need to allocate the save and parameter areas from
the OS. First, you'll have to allocate them from someplace, and
second passing parameters via the R1 list painful for the vast
majority of short parameters that are passed by value. Then
maintaining the linkagae is more expensive than necessary (while C++
does require a back chain in order to unwind exceptions, it does need
the forward chain), and you're forced to save too many registers. In
XPLink, for example, you can pass several parameters in registers, you
don't need two areas to manage, there's no forward chain, and the
number of registers saved is usually considerably less.

If the R13 convention was a good one in general, people wouldn't spend
so much time avoiding it. Even traditional assembler or HLL usage on
S/360, et al, usually avoided that internally. Almost never did you
see an internal subroutine call in an assembler program do the full
save area thing (yes, there were time when it was appropriate).
Likewise internal calls in Cobol and Fortran tended to use their own
mechanism as well. That is, of course, true on many platforms,
there's a standard ABI, but it's only followed at boundaries beteween
components - many compilers will optimizse the calling convention at
points where they can decide that following the stanbard ABI is not
necesary (for example, if a routine is only called from inside a
program). And that true even though most platforms "standard" ABI are
not nearly as painful as the S/360 one.

>>> It can easily do the same by subdividing an existing storage. It could
>>> easily use linked lists for this. When I worked for IBM, we did a lot
>>> of assembler this way, including recursive routines. And we almost
>>> never had to request more storage from the OS.
>>>
>>> And no, the R13 linked list format is *not* just used for functions that
>>> call or are called from the outside. It is used quite extensively with
>>> internal calls also - including setting up the above pseudo-stack.
>>
>>
>> In the context of C or C++ programs, the traditional S/360 method is
>> not used for most internal calls. You generally need to specify
>> traditional linkage explicitly (via either #pragma linkage or a
>> specification on the extern statement) on those functions where it's
>> needed. At least for normal C/C++ since the later OS/390 days. The
>> (normally used) XPLink convention uses R4 to address a typical
>> "hardware-style" stack, and reserves various registers for passing
>> parameters and return values.
>>
>
>That depends on which compiler you are using. There is no "standard"
>(as there is in the R13 save area standard).

XPLink is a standard, it's not followed everywhere. There are (like
on many platforms) a number of "standard" calling conventions on
mainframes (the LE convention, the OS (R13) conventions plus a stack,
the PL/I modification of the standard OS convention, etc.) The point,
however, is that the notion that the S/360 R13 convention is most
common inside C or C++ programs is wrong.

[red floyd]

The TI 34010 Graphics processor communicated with the host CPU via
memory mapped registers. You'd load the address register with the
address in 34010 memory space, and then write to the data register.
Successive writes would increment the address register, so that you
could load graphics data by successive writes to the data register.

[Jerry Stuckle]

Sure, just as you have to allocate space for a stack from someplace. No
difference there. And passing parameters via R1 may be "painful" to you
- but it is standardized and very flexible - any number of any types of
parameters can be passed, for instance. Linkage isn't hard at all -
backward pointers, no forward pointers required (although you can use
one - a single instruction). As for "storing too many registers" - it's
one statement to store 15 registers (stm 14, 12, 12(13)). Even easier
than having to push multiple registers onto a stack individually.

But XPLink requires potentially different linkage for every function,
different register usage and even storing individual registers instead
of all at once. And then you need to keep track of registers which
haven't been saved - and ensure those aren't used. Not so with the R13
convention - all registers are available (with only R13 reserved to
point to the save area).

> If the R13 convention was a good one in general, people wouldn't spend
> so much time avoiding it. Even traditional assembler or HLL usage on
> S/360, et al, usually avoided that internally. Almost never did you
> see an internal subroutine call in an assembler program do the full
> save area thing (yes, there were time when it was appropriate).
> Likewise internal calls in Cobol and Fortran tended to use their own
> mechanism as well. That is, of course, true on many platforms,
> there's a standard ABI, but it's only followed at boundaries beteween
> components - many compilers will optimizse the calling convention at
> points where they can decide that following the stanbard ABI is not
> necesary (for example, if a routine is only called from inside a
> program). And that true even though most platforms "standard" ABI are
> not nearly as painful as the S/360 one.
>

Actually, that is not at all true. We did it all the time at IBM. We
even had macros that would do the whole works for us. And our customers
used the convention, also.

As for COBOL and FORTRAN - I don't know about other compilers, but the
IBM compilers used it. It was one of the internal standards IBM
expected to be followed by all programmers - because it's good and it works.

>
>>>> It can easily do the same by subdividing an existing storage. It could
>>>> easily use linked lists for this. When I worked for IBM, we did a lot
>>>> of assembler this way, including recursive routines. And we almost
>>>> never had to request more storage from the OS.
>>>>
>>>> And no, the R13 linked list format is *not* just used for functions that
>>>> call or are called from the outside. It is used quite extensively with
>>>> internal calls also - including setting up the above pseudo-stack.
>>>
>>>
>>> In the context of C or C++ programs, the traditional S/360 method is
>>> not used for most internal calls. You generally need to specify
>>> traditional linkage explicitly (via either #pragma linkage or a
>>> specification on the extern statement) on those functions where it's
>>> needed. At least for normal C/C++ since the later OS/390 days. The
>>> (normally used) XPLink convention uses R4 to address a typical
>>> "hardware-style" stack, and reserves various registers for passing
>>> parameters and return values.
>>>
>>
>> That depends on which compiler you are using. There is no "standard"
>> (as there is in the R13 save area standard).
>
>
> XPLink is a standard, it's not followed everywhere. There are (like
> on many platforms) a number of "standard" calling conventions on
> mainframes (the LE convention, the OS (R13) conventions plus a stack,
> the PL/I modification of the standard OS convention, etc.) The point,
> however, is that the notion that the S/360 R13 convention is most
> common inside C or C++ programs is wrong.
>

Yes, it's a relatively new standard. I don't know what IBM has changed
internally since I left many years ago. But you still haven't proven
XPLink is any more or less used than R13. Only what you have seen,
which is just a small part in the world of programming.

I haven't seen that much more than you have - but I do have the benefit
of years of programming experience with IBM, and know what their
standards were at the time, anyway.

[Wouter van Ooijen]

Op 20-Apr-16 om 12:57 AM schreef Jerry Stuckle:

> On 4/18/2016 6:39 PM, Alf P. Steinbach wrote:
>> On 18.04.2016 22:07, Vir Campestris wrote:
>>> On 18/04/2016 03:12, Alf P. Steinbach wrote:
>>>> On 18.04.2016 03:59, Jerry Stuckle wrote:
>>>>>
>>>>> But C does not require a stack. Only a way to create a
>>>>> unique storage area when a function is called.
>>>>
>>>> That is a stack.
>>>
>>> Well, that could equally well be a heap.
>>
>> No, a heap doesn't have LIFO behavior. The LIFO behavior for the
>> allocations and deallocations is forced by the languages' support for
>> general recursion, which can generate arbitrary long chains of stack
>> frames for the call stack. The C++ standard refers to it as a stack, and
>> we use terms such as “stack frame” and “call stack”, because it's a
>> stack, regardless of the implementation details.
>>
>>
>> Cheers & hth.,
>>
>> - Alf (nonsense fighter)
>>
>
> So then please tell us - how does one implement C on an IBM mainframe -
> which does have a stack pointer nore does it support push, pop, call,
> return, etc. instructions?

As a last resort, write a Java VM and use gcc with a Java backend (write
one, if it doesn't exist).

Wouter "Objects? No thanks!" van Ooijen

[Jerry Stuckle]

So is that how they run Linux on an IBM mainframe?

> Wouter "Objects? No thanks!" van Ooijen
>