D
Dik T. Winter
Right. And this is done in Fortran 77. On the other hand, the system
may provide a different stack for each function.
Right. And this is done in Fortran 77. On the other hand, the system
may provide a different stack for each function.
D
Dik T. Winter
If I remember right Jack Klein said the stack pointer on the 8051 is
not accessible. And he is (I think) right. You can only retrieve
the byte on top of the stack, and you can only push and pop single
byte variables in internal memory.
Ah. But the OP asked
(1) Why does C insist that local variables are on the stack
and
(2) Why are local variables not allocated on the heap.
J
jacob navia
Kenneth said:
< quote >
* The datatypes float and double are not available.
* The compiler does not support bit fields.
* C functions may not return structs and structs may not be passed as
parameters by value.
< end quote >
This is not a conforming compiler
Because they are so crippled that they are not conforming
See above
K
Keith Thompson
jacob navia said:
That's true (and it's a good point), but its areas of nonconformance
do not include a failure to support recursion.
[snip]
jacob, you still haven't responded to my questions about the IBM
mainframe system whose documentation you cited. In particular, though
it uses a register to manage the current "stack frame", there's no
indication that "stack frames" are allocated contiguously, and it's
been stated that they are not. I believe this is the example that you
claim doesn't exist. Do you have a response?
J
jacob navia
Keith said:
Well, please READ the docs in the link I gave.
There, you will find:
5.1.3.5 Setting up a C VM/ESA Environment with Preallocated Stack and Heap
Subtopics:
* 5.1.3.5.1 EDCXSTRX
This is a routine that is the ENTRY point of the program.
Unlike the system routine, this one doesn't allocate automatically
the stack, and you need to allocate it and pass it to this
startup routine. Specifically the documentation for parameter
(2) is:
< QUOTE >
The address of the initial storage area. This area must be doubleword
aligned with its first word containing its total length. It must be
large enough to accommodate the entire stack requirements of the
application.
< END QUOTE >
You see?
1) The stack is a SINGLE CONTIGUOUS MEMORY AREA
2) It is accessed by the dedicated register R13.
If you use the default system entry point, the preallocation
is done by the system somehow, and you can't control how
much stack you have. This routine allows you to allocate
more stack than the default. This is 100% similar to MANY
other systems where the stack is managed by convention without any
CPU mandated stack pointer.
Q.E.D
Corollary:
The people that are telling stories here do not have a clue!
I hope that this is definitely OVER and we can agree that there
isn't a SINGLE EXAMPLE of a C implementation without a stack!
P
Paul Hsieh
That's called equivocation. In the most general meaning of the word
stack, or the standard computer science version, C has a stack. It
may be implicit and not described as such in the standard, but its
still definitely there.
Whether its encoded in pieces over several memory locations, or in
hardware registers or whatever, it doesn't matter. Locals inside of a
functions scope are only available if its runtime context has been
pushed onto the call stack (i.e., the function has been called) and
are removed once the context has been popped. I.e., the local
lifetime is in direct correspondence with an existing call stack.
There is a topological stack; the standard *does* insist on it.
What you and others are trying to make excuses for, is some hardware
vendor's labeling of a hardware stack as just "the stack"; I am
thinking of Intel's documentation. This is very ironic, because even
Intel encodes multiple stacks: one is an auto-incrementing memory
based call stack, and another is a fixed sized 8-entry FPU value
stack. This is nonsense -- its just the implicit endorsement of some
interpretation of corporate documentation over general computer
science.
I don't know what this means, unless you are implicitly endorsing
Intel's or Dec's or someone's definition of a stack that's different
from the one in computer science. The sequence of locals and return
links forms a stack.
To show that its not a stack, you would have to demonstrate that you
could remove a deeper set of locals *before* a shallower set, or that
you can reorder their lifetime, or that you could follow the return
sequence out of the pop-stack order (where obviously a longjmp is
topologically equivalent, from the stack's point of view, to calling
multiple returns in sequence) or something very much like that. If
you don't do that, I don't know what it means to claim that "C does
not insist on storing local variables on a stack". Do you mean
variables are not stored? And is that an equivocation on the word
"variable" or the word "stored"?
Showing that the implementation might be different (or that it might
do something like the above listed violations *internally* via the "as-
if rule") does not demonstrate that its not a stack.
No, those responses are just technically wrong. Its like saying that
ice cubes are not cubes because they can be made of various kinds of
water.
P
Paul Hsieh
Well -- most compilers actually will throw local variables into
registers as well. So they usually *use* a hardware stack in general,
however, they also usually extend it into non-HW stack registers.
A "hardware stack" is not equivalent to the C stack. If you say "the
stack" in this newsgroup, you must be referring to the ANSI C implicit
stack right? If you mean the *x86* stack, then you should say so.
Right, and the answer is: Because that's what the specification
implicitly defines. Its a perfectly sound design; I assume it was
done this way following the success of most other programming
languages which do something very similar.
I mean is the original question really oriented around the x86 stack
or something? I mean isn't this obviously irrelevant by the coverage/
scope of the ANSI C standard? If we were to consider different
implementations/platforms, can someone give a real example, in C code,
of how this claim that C does not use a stack can be made clear?
It is? How so? Are you saying variables are not stored? Or not in a
stack (that happens to be topologically interleaved with the call
stack)?
Well good for him, I will too. That's not a correct response.
I guess since people still keep insisting that there is no stack in C
for some reason that I cannot fathom.
I'm curious, in what sense are variables not stored? In what sense
are their lifetime not governed by and one to one correspondence to
entries on the (call) stack? What is the substance of the other side
of this argument? I just don't get it.
U
user923005
Side note:
Microsoft has supported long long for about 4 years now:
C:\tmp>cl /W4 /Ox tt.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762
for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
tt.c
Microsoft (R) Incremental Linker Version 8.00.50727.762
Copyright (C) Microsoft Corporation. All rights reserved.
/out:tt.exe
tt.obj
C:\tmp>tt
4611686018427387904 1152921504606846976
C:\tmp>type tt.c
#include <stdio.h>
#include <math.h>
int main(void)
{
long long llv;
unsigned long long ullv;
llv = (long long) floor(pow(2.0, 60.));
ullv = 1ULL << 62;
printf("%llu %lld\n", ullv, llv);
return 0;
}
L
lawrence.jones
jacob navia said:
That's all correct, but you've misunderstood it. While R13 does point
to the current "stack frame" (which is a bit of a misnomer, most
computer scientists would use the term "activation record" instead),
those "stack frames" are *not* stored contiguously in memory. Rather,
they are allocated individually (from the heap) and chained together
into a doubly-linked list in a LIFO fashion. Thus, R13 is not simply
incremented and decremented on entry and exit like a traditional stack
pointer, but is rather saved and restored like the other registers. (It
is interesting to note, however, that R13 is stored in the current
function's "stack frame" whereas the other registers are stored in the
*caller's* "stack frame". That is because the other registers must be
saved prior to allocating the new stack frame, since that process
requires using some of the registers, but R13 must be saved in the
current "stack frame" in order to be able to find the previous "stack
frame" where the other registers are stored.)
-Larry Jones
Hmm... That might not be politic. -- Calvin
J
jacob navia
You are wrong.
(1)
All activation records save the current frame pointer value in a linked
list. I do this in the code generated for the x86, x86(64) power PC
and solaris back ends of lcc-win. This is even if all the stack is a
single memory area!
(2)
The startup procedure install the stack where R13 points
to. And that stack must be allocated previously and be contiguous. Look
at the custom entry point (as I indicated to K Thompson)
(3)
There is no mention of any linked list anywhere in the docs I have
Where did you got this linked list allocation story?
(4)
Can you imagine the incredible resource waste that would be to call
malloc at each function call ???? Just think a bit about that.
Think about the supposed call to "malloc" to allocate a stack
frame. How would that work in the "malloc" function?
Please stop telling us stories or bring a piece of docs that
substantiate your wild claims!
---------------------------------------------------------------------
And please READ the docs in the link I gave.
There, you will find:
5.1.3.5 Setting up a C VM/ESA Environment with Preallocated Stack and Heap
Subtopics:
* 5.1.3.5.1 EDCXSTRX
This is a routine that is the ENTRY point of the program.
Unlike the system routine, this one doesn't allocate automatically
the stack, and you need to allocate it and pass it to this
startup routine. Specifically the documentation for parameter
(2) is:
< QUOTE >
The address of the initial storage area. This area must be doubleword
aligned with its first word containing its total length. It must be
large enough to accommodate the entire stack requirements of the
application.
< END QUOTE >
You see?
1) The stack is a SINGLE CONTIGUOUS MEMORY AREA
2) It is accessed by the dedicated register R13.
If you use the default system entry point, the preallocation
is done by the system somehow, and you can't control how
much stack you have. This routine allows you to allocate
more stack than the default. This is 100% similar to MANY
other systems where the stack is managed by convention without any
CPU mandated stack pointer.
Q.E.D
Corollary:
The people that are telling stories here do not have a clue!
I hope that this is definitely OVER and we can agree that there
isn't a SINGLE EXAMPLE of a C implementation without a stack!
W
Willem
Paul wrote:
) A "hardware stack" is not equivalent to the C stack. If you say "the
) stack" in this newsgroup, you must be referring to the ANSI C implicit
) stack right? If you mean the *x86* stack, then you should say so.
The question was "why does C insist that variables are stored on the stack"
so 'the stack' in that context *cannot* mean 'the place the auto variables
are stored', because otherwise the question would be a tautology.
Reading further into the OP, it becomes obvious that 'the stack' in this
context means the call/return stack, where most C implementations do indeed
store most of the auto variables, but _that is not required_.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
) A "hardware stack" is not equivalent to the C stack. If you say "the
) stack" in this newsgroup, you must be referring to the ANSI C implicit
) stack right? If you mean the *x86* stack, then you should say so.
The question was "why does C insist that variables are stored on the stack"
so 'the stack' in that context *cannot* mean 'the place the auto variables
are stored', because otherwise the question would be a tautology.
Reading further into the OP, it becomes obvious that 'the stack' in this
context means the call/return stack, where most C implementations do indeed
store most of the auto variables, but _that is not required_.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
D
Dik T. Winter
EDCXSTRX
"This module is the mainline for applications that receive a
structured parameter list that includes preallocated storage
management areas."
In what way is that normal for standard applications? You should want
to know what the macro CEESTART does do.
Actually, a stack as normally implemented is also a linked list
allocation story.
But see the description in 5.2.2. But most of all, see 5.1.5.2, figure
52 note 1:
"This routine is entered with standard linkage conventions. It saves
the registers in the save area pointed to by register 13, acquires
a dynamic storage area for its own use, and chains the save areas
together."
The dynamic allocation is done by
GETMAIN R, LV=D3ALEN
If it quacks...
The malloc function is not necessarily written in C.
K
Keith Thompson
jacob navia said:
Perhaps later. Since you're the one making the claim, you should post
excerpts that actually support your claim; your earlier, excerpt, at
least, did not.
Sorry, I'm afraid I don't have time to go into much detail. In any
case, I think Dik T. Winter knows this stuff better than I do.
No, why would I agree to that? You have *at most* demonstrated a
single implementation that uses a contiguous stack. As I've pointed
out at least twice before, there have been multiple C implementations
under multiple operating systems on multiple models of IBM mainframes.
K
Keith Thompson
Paul Hsieh said:
No, it's called precision.
The word "stack" is a common English word (derived from the Middle
English "stac", from the Old Norse "stakkr"). Computer science has
appropriated the word for its own specialized purpose, to refer to a
last-in first-out data structure. Computer architecture has
appropriated the word for a similar specialized purpose, to refer to a
contiguous region of memory allocated in a certain way (insert a more
rigorous description here).
I'm not making excuses for anything. I agree that it's too bad that
the word "stack" is used in two such confusingly similar way (see also
"heap"). We're seeing the result of that confusion in these
interminable threads.
It's very clear that the original poster was using the word "stack"
the way Intel does; otherwise the question wouldn't make sense.
If you want to argue that Intel's use of the word "stack" is incorrect
because it conflicts with the computer science usage of the term, go
ahead; I won't necessarily disagree with you. But, right or wrong,
that usage of the word is firmly entrenched (and not just by Intel).
I *can't* make everybody use the word in only one way, and I *won't*
pretend that the common usage doesn't exist.
[...]
That's a strawman argument. I've lost track of the number of times
that I've said that C *does* implicitly require a "stack" in the
computer science sense of a LIFO data structure.
[...]
It's like saying (in fact, it is saying) that the C language, though
it implicitly requires a LIFO mechanism to manage automatic storage
(or at least requires programs to behave *as if* there is such a
mechanism), it does not require a contiguous hardware stack that grows
in a particular direction (what Intel, correctly or incorrectly, calls
"the stack"). If you want to suggest a better way to express that
distinction *without* ignoring the fact that people use the word
"stack" in at least two different ways, please do so.
J
Jean-Marc Bourguet
Keith Thompson said:
Well, nothing prevents an implementation to dynamically allocate the
activation records and then garbadge collect them. This to make something
like
int *newInt() {
int i;
return &i;
}
having a reasonnable implementation defined behavior
Not really in thespirit of C, but not impossible if it is a side effect of sharing the back
end of the compiler with a language having proper closures. Obviously, one
of the first optimization done by such a back end would be to use the
hardware stack if available for the activation records which don't need
dynamic allocation because they are not leaked. So the performance cost
of the feature would be quite minimal for properly written C.
A+
L
lawrence.jones
jacob navia said:
It's certainly common, but it's by no means universal. If you don't
allow variable dynamic stack allocation (e.g., alloca), the start of the
frame is always a known offset from the current stack pointer, so
there's no need for a separate frame pointer. And since the frame is a
fixed size, there's no need to save and restore the stack pointer,
either; just increment (or decrement, depending on which way the stack
grows) it by the fixed size on entry and decrement it by the same size
on exit.
You're again quoting text without understanding the context. The
section you're quoting is talking about creating and using non-standard
run-time environments; it's not talking about the standard C run-time
environment which is now integrated into the common IBM Language
Environment:
<http://publibfp.boulder.ibm.com/cgi-bin/bookmgr/BOOKS/CEEU1007/4.3.2?SHELF=&DT=19950913203351>
Note in particular:
4.3.2 Stack Storage Overview
The user stack is used by both library routines and compiled
code. Stack storage is also available in the library stack,
which is an independent area of stack storage, allocated below
the 16M line, designed to be used only by library routines.
So already it's clear that there isn't a single contiguous stack since
there is a separate stack available for library functions.
The storage stack is divided into large segments of storage
called stack segments, which are further divided into smaller
segments called stack frames (8), also known as dynamic storage
areas (DSAs). A stack frame, or DSA, is dynamically acquired
storage composed of a register save area and an area available
for dynamic storage allocation for items such as program
variables. ...
The first segment used for stack storage is called the initial
stack segment. When the initial stack segment becomes full, a
second segment, or stack increment is obtained from the
operating system. As each succeeding stack increment becomes
full, another is obtained from the operating system as needed.
So here we have the full picture: even the user stack isn't contiguous,
it's made up of a number of disjoint segments allocated from the OS
(i.e., the heap). If the segment size is small enough, each stack frame
will be separately allocated and thus disjoint. (Early implementations
of IBM C allocated each stack frame individually, which is what I based
my original comments on. Other mainframe compilers that I have used
[AT&T and SAS] worked similarly.)
That's part of the OS standard linkage convention that's implied when
the above refers to "register save areas". See:
said:
Nonetheless, that's essentially what most mainframe systems do/did.
Most mainframe code is not recursive, so each function can simply have a
statically allocated "stack frame". Languages that do allow recursion
pay the price by having to dynamically allocate their "stack frames".
(Although it's also possible for the compiler to use a statically
allocated "stack frame" for any function that doesn't make any function
calls.)
In this case, "malloc" is a system service, not the actual C function
(although the actual C function calls the same system service). And
like I said, that's why it's the *caller's* responsibility to allocate
space for the callee to save the registers in -- the callee has to save
the registers before it's had a chance to allocate its stack frame.
-Larry Jones
Everybody's a slave to routine. -- Calvin
P
Paul Hsieh
Its only tautological, if you already know the answer. But a teacher
or other environment will typically refer to "the stack" or something
of that nature in C or other languages while not explaining to the
student that the stack is resultant, not an a priori structure that is
prerequisite.
Yeah ok, but that means his question makes a semantic confusion that
some people here, for some reason, are buying into.
P
Paul Hsieh
You are using the word precision to describe "I think we both
understand what he means by it"? What is this, alt.satire or
something?
In any event, that's besides the point. If you wish, I will grant
that you are being precise -- in fact you are elucidating your
equivocation very precisely by repeating your mistake over and over.
No, seriously. Look up the word equivocation in the dictionary.
That's exactly what this is. That's clearly irrelevant, and
transparently so. Nobody here thinks were are talking about book
stacks or anything like that.
What the hell are you talking about? Computer architecture inherits
the computer science definition. It doesn't create a new one. A CPU
can implement a stack, and thus have its own stack, but that does not
dictate how a computer language is going to formulate its stack.
The confusion is a matter of perspective. You are implicitly bringing
in a vendor's CPU implementation of the stack, while ignoring the C
language defined stack. *In this newsgroup* that you, among others,
insist must not deviate from discussing C.
In this case, I endorse the distinction of the implicit stack, because
the details of a hardware stack are rarely relevant to any compiler.
Also, modern compilers heavily make use of the as-if rule, to simplify
and even eliminate the storage of certain auto-variables, making the
mapping to hardware implementation truly meaningless.
Yeah ok, but that's a mistake.
It isn't *intrinsically* wrong, its just wrong *HERE*. The CPU stack
is *AN* implementation of a stack. So from their point of view, its
perfectly valid to call it a stack or the CPUs stack, or if talking
about a specific CPU, "the stack". And if this were comp.lang.asm.x86
or comp.arch or comp.compilers or something like that, then that seems
like a valid thing to discuss.
Oh don't worry about that. I can trace back to when you original
started saying this. I think we both know exactly when that was.
Yeah there's a simple way. Just be consistent, and in CLC, the stack
is the stack that is implicitly defined by the language. There's no
controversy if you do that, because its technically correct without
introducing any new or restrictive semantics, meaning or terminology.
Also because the correctness rate of anything else said about stacks
in this newsgroup, even in this thread alone is so ridiculous low,
that there's nothing of any substance lost in rejecting that alternate
form of discourse.
K
Keith Thompson
Paul Hsieh said:
If I understand you correctly, you're saying that, at least in the
context of this newsgroup, the word "stack" can only refer to the
computer science concept of an abstract LIFO data structure, and that
using the word to refer to a particular contiguous hardware
implementation is wrong.
In my opinion, both uses of the term are legitimate. One of those
meanings is applicable to the C language, at least to the C abstract
machine. The other is not, but is applicable only to particular
implementations (most of them, as it happens).
My point in citing the derivation of the word was that "stack", like
any word, can and does have different meanings in different contexts.
I respect your opinion that one meaning is correct and the other is
wrong, but I don't share that opinion. As far as I can tell, that
disagreement (which I think is a minor one) is what's motivated you to
flame me rather than, say, try to help answer the OP's question.
[snip]
No. I *explicitly* discussed a vendor's CPU implementation of the
stack (and it's not just one vendor; I first encountered the concept
on the PDP-11, and most CPUs support something similar). I did so
because the original poster *implicitly* used the term "stack" in that
sense.
As for "ignoring the C language defined", perhaps you're confusing me
with somebody else, because I've discussed it at considerable length.
Huh? They're not relevant to the language, but they're extremely
relevant to any compiler that has to generate code that uses it.
Yes, of course.
It's not completely meaningless, but it's outside the scope of the
language.
Which you could have corrected rather than flaming me.
[snip]
Perhaps you do. Maybe you've kept better track of what I've written
here than I have. I have no idea what point you're trying to make.
I said "*without* ignoring the fact that people use the word 'stack'
in at least two different ways". If you want to ignore that fact, go
ahead; I'd rather acknowledge it and help people understand what's
really going on.
D
David Thompson
#if offtopic = further and further
Do you really mean doubly-linked? It would make no sense to link both
directions (logically 'up' and 'down'). Some _other_ languages with
nested routines (notably PL/I) require both dynamic (call) and static
('lexical') links, but that's not what I normally call doubly-linked.
- formerly david.thompson1 || achar(64) || worldnet.att.net
Do you really mean doubly-linked? It would make no sense to link both
directions (logically 'up' and 'down'). Some _other_ languages with
nested routines (notably PL/I) require both dynamic (call) and static
('lexical') links, but that's not what I normally call doubly-linked.
- formerly david.thompson1 || achar(64) || worldnet.att.net