gardner@prls.UUCP (Robert Gardner) (11/14/87)
Is there any danger of stack overflow with the following construct:
for(;;) {
int k;
etc. etc.
}
(assume the loop eventually exits, of course).
In other words, is k allocated only once at the beginning of the
procedure containing this construct, or is it allocated each time
the {} block is entered? Is the answer implementation dependent?
Robert Gardnerchris@mimsy.UUCP (Chris Torek) (11/15/87)
In article <7401@prls.UUCP> gardner@prls.UUCP (Robert Gardner) writes: >Is there any danger of stack overflow with the following construct: >for(;;) { > int k; > etc. etc. >} No. >In other words, is k allocated only once at the beginning of the >procedure containing this construct, or is it allocated each time >the {} block is entered? Is the answer implementation dependent? The answer is implementation dependent, but if a loop like for (;;) { int k; } runs for several minutes, then produces a stack overflow, the implementation is horrible. For example, a very straightforward compiler might generate this: proc() { int a, b; for (;;) { int k; if (g()) break; } a = 1; } -------- _proc: sub $8,sp | create local variables a, b L1: sub $4,sp | create local variable k call _g | run g tst r0 | what was g's return value? bne L3 | nonzero, break loop L2: add $4,sp | destroy local variable k bra L1 | back around the loop L3: add $4,sp | destroy local variable k mov $1,-4(sp) | a = 1 L0: add $8,sp | destroy locals a, b ret Label `L2' above is for a `continue' that might appear inside the for loop. It is not used, but so what? Likewise, L0 is allocated at the beginning of code generation for proc(), in case there are any `return' statements in it. I optimised away the sequence a truly dumb compiler would probably emit for `if (g()) break'. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
new@udel.EDU (Darren New) (11/15/87)
In article <7401@prls.UUCP> gardner@prls.UUCP (Robert Gardner) writes: >Is there any danger of stack overflow with the following construct: >[code with allocation of local inside a for-loop block here] >In other words, is k allocated only once at the beginning of the >procedure containing this construct, or is it allocated each time >the {} block is entered? Is the answer implementation dependent? > >Robert Gardner Most compilers I've seen allocate it once at the beginning of the function. If there are multiple blocks with local variables, these definitions overlap. EG: {int k; k = 3;} {int w; w = 77;} would put K and W in the same place. However, even if the variable is allocated on each entry, it will be deallocated at the end of each loop. Thus, no stack problems. (Of course, recursive functions are something else.) Darren New @ UDel
daveb@laidbak.UUCP (Dave Burton) (11/18/87)
In article <7401@prls.UUCP> gardner@prls.UUCP (Robert Gardner) writes: >Is there any danger of stack overflow with the following construct: > >for(;;) { > int k; > etc. etc. >} >(assume the loop eventually exits, of course). >In other words, is k allocated only once at the beginning of the >procedure containing this construct, or is it allocated each time >the {} block is entered? Is the answer implementation dependent? In response to your more general question (subject line), the answer is: Local (auto) variables in C are placed on a stack dynamically at function invocation time. This is the reason you cannot rely on the initial value of such a variable without an explicit initializer. These locals are destroyed upon return from the function. The usual implementation in a stack oriented computer is to point some register to the current stack location, then subtract a constant to the stack pointer to create an empty region which the locals will inhabit. Upon return, the stack pointer will be reset to the saved location, and the arguments 'popped' off (quite often, the popping action is accomplished by adding a value equivalent to the amount of storage required by the argument). Blocks '{statement;...}' define a new scope, but not a new invocation. Most compilers will create room for variables defined in a block when space is allocated for the function's local variables. Even if some implementation behaves this way, you are guaranteed the auto variable will be destroyed upon exit from the block, in the same manner as that described above. Your for loop is an example of a block. As a further example, the following program: main() { int a; a = 2; { int a; a = 1; printf("%d\n", a); } printf("%d\n", a); } produces the (unsurprising) output: 1 2 The variable 'a' in the inner block has a different scope than the variable in the outer block (main()). It is in a different 'name space'. My compiler (pcc based 68k) reserves room on the stack upon entry to the function main() via the link instruction, and destroys this room upon return via unlk. Machines without such instructions typically add and subtract compile-time calculated values from the stack pointer. This is correct for a K&R and ANSI conforming compiler. Be warned that not all compilers behave properly with name spaces, however, and the above program may not work due to symbol redefinition. (BTW, if you name your variables in like manner, you get what you deserve.) -- --------------------"Well, it looked good when I wrote it"--------------------- Verbal: Dave Burton Net: ...!ihnp4!laidbak!daveb V-MAIL: (312) 505-9100 x325 USSnail: 1901 N. Naper Blvd. #include <disclaimer.h> Naperville, IL 60540
djones@megatest.UUCP (11/19/87)
in article <9367@mimsy.UUCP>, chris@mimsy.UUCP (Chris Torek) says: > > In article <7401@prls.UUCP> gardner@prls.UUCP (Robert Gardner) writes: >>Is there any danger of stack overflow with the following construct: >>for(;;) { >> int k; >> etc. etc. >>} > > No. > >>In other words, is k allocated only once at the beginning of the >>procedure containing this construct, or is it allocated each time >>the {} block is entered? Is the answer implementation dependent? > > The answer is implementation dependent, but if a loop like > > for (;;) { > int k; > } > > runs for several minutes, then produces a stack overflow, the > implementation is horrible. For example, a very straightforward > compiler might generate this: > > proc() > { > int a, b; > > for (;;) { > int k; > if (g()) > break; > } > a = 1; > } > -------- > _proc: > sub $8,sp | create local variables a, b > L1: > sub $4,sp | create local variable k > call _g | run g > tst r0 | what was g's return value? > bne L3 | nonzero, break loop > L2: > add $4,sp | destroy local variable k > bra L1 | back around the loop > L3: > add $4,sp | destroy local variable k > mov $1,-4(sp) | a = 1 > L0: > add $8,sp | destroy locals a, b > ret > > Label `L2' above is for a `continue' that might appear inside > the for loop. It is not used, but so what? Likewise, L0 is > allocated at the beginning of code generation for proc(), in > case there are any `return' statements in it. I optimised away > the sequence a truly dumb compiler would probably emit for > `if (g()) break'. > -- > In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) > Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris I wasn't going to answer, but this is just TOO silly. (Don't feel bad. The world needs some silliness from time to time.) 8-] The answer is, "No the stack will not overflow." If an explanation is required, it might be, "The variable k retains its value on each iteration, so no copy of it is needed. (Procedure local variables, unlike in FORTRAN for example, are not retained between procedure activations, and so new memory for them must typically be allocated on the stack.)" By the way, some compilers will produce code to use only one memory cell for all the variables k (one per procedure activation) implied by the execution of the following procedure, even when k > 0. It's called "removing tail-recursion." Wow. :-) foo(k) { if(k==0) return; else { /* etc. */ foo(k-1); } }
msb@sq.UUCP (11/22/87)
There have been several followups regarding the code:
for (;;) {
int k;
...
}
but I think they have each either left out an important point, or wandered
at length into side issues. So let me try.
The above requests that a new variable "k" be created, and destroyed
again, on each iteration of the loop. Since it is destroyed each time,
obviously it can't cause a stack overflow after many iterations.
Any sensible compiler will implement the creation and destruction
virtually, which is to say, any actual stack operations will take place
either when the loop is entered for the first time and exited for the last
time, or when the function is entered and exited. Or perhaps "k" will be
put in a register and there will be no stack operations at all.
But the value of "k" is NOT guaranteed to be retained from one iteration
to the next, and you must not assume it will be. If you want that, you
have to declare "k" in a larger scope including the for-header.
Mark Brader, SoftQuad Inc., Toronto, utzoo!sq!msb, msb@sq.com
"Have you ever heard [my honesty] questioned?"
"I never even heard it mentioned." -- Every Day's a Holidayreggie@pdnbah.UUCP (George Leach) (11/24/87)
In article <1987Nov22.085210.20641@sq.uucp> msb@sq.UUCP (Mark Brader) writes: >There have been several followups regarding the code: > for (;;) { > int k; > ... > } >but I think they have each either left out an important point, or wandered >at length into side issues. So let me try. [stuff deleted concerning allocation and deallocation of the variable k and what might actually be implemented by a compiler....... >But the value of "k" is NOT guaranteed to be retained from one iteration >to the next, and you must not assume it will be. If you want that, you >have to declare "k" in a larger scope including the for-header. Or you can declare it static: for (;;) { static int k; ^^^^^^ ... } George W. Leach Paradyne Corporation {gatech,rutgers,attmail}!codas!pdn!reggie Mail stop LF-207 Phone: (813) 530-2376 P.O. Box 2826 Largo, FL 34649-2826
richardh@killer.UUCP (11/26/87)
In article <1987Nov22.085210.20641@sq.uucp>, msb@sq.uucp (Mark Brader) writes: > There have been several followups regarding the code: > > for (;;) { > int k; > ... > } > ... > The above requests that a new variable "k" be created, and destroyed > again, on each iteration of the loop. Since it is destroyed each time, No it doesn't! It requests that a variable "k" be allocated and be visible for the duration of execution of the block defined by the "{}" pair. To quote H&S: "An object is said to have _local extent_ when (in the case of C) it is created upon entry to a block or function and is destroyed upon exit from the block or function." p. 57, sec. 4.2.7, third paragraph, ed. 1. Even if it is allocated on entry to the block, it will only be allocated once. As has been pointed out, many compilers actually allocate the storage upon entry to the function and limit the object's visibility to the defining block. > > But the value of "k" is NOT guaranteed to be retained from one iteration > to the next, and you must not assume it will be. If you want that, you Yes it is! The variable's scope is the block in which it is defined. richard hargrove ...!killer!richardh ------------------- Found on a Post-It attached to the front of a terminal in a deserted office in downtown Wichita: "Aunty Em, Hate you. Hate Kansas. Took the dog. Dorothy" ---------------------------------------------
chris@mimsy.UUCP (Chris Torek) (11/27/87)
In article <2218@killer.UUCP> richardh@killer.UUCP (Richard Hargrove) writes a bunch of stuff that quotes H&S correctly, but misinterpets something somewhere: >> for (;;) { >> int k; >> ... >... requests that a variable "k" be allocated and be visible >for the duration of execution of the block defined by the "{}" pair. Good so far. >Even if it is allocated on entry to the block, it will only be allocated >once. It will be `allocated' each time you enter the block. When do you enter the block? Answer: once for each trip around the loop: this is probably more than once. >As has been pointed out, many compilers actually allocate the storage upon >entry to the function and limit the object's visibility to the defining >block. Right again. >>But the value of "k" is NOT guaranteed to be retained from one iteration >>to the next, and you must not assume it will be. (The >> text is by Mark Brader, msb@sq.UUCP, and is correct.) >Yes it is! The variable's scope is the block in which it is defined. The scope is indeed the block in which it it is defined. Here is an example of *incorrect* usage: int i; for (i = 0; i < 10; i++) { int j; if (i == 0) j = 1; else j *= i; ... } This uses the undefined value of `j' for all but the first trip around the loop. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
gwyn@brl-smoke.ARPA (Doug Gwyn ) (11/27/87)
In article <2218@killer.UUCP> richardh@killer.UUCP (Richard Hargrove) writes: >> But the value of "k" is NOT guaranteed to be retained from one iteration >> to the next, and you must not assume it will be. If you want that, you >Yes it is! The variable's scope is the block in which it is defined. No, execution leaves (and re-enters) the block statement each iteration of the loop. The variable goes out of scope each time the block is left.
msb@sq.UUCP (11/27/87)
> >But the value of "k" is NOT guaranteed to be retained from one iteration > >to the next, and you must not assume it will be. If you want that, you > >have to declare "k" in a larger scope including the for-header. > > Or you can declare it static: > for (;;) { > static int k; > ... > } True, but then there's only one copy of k even if the function is re-called recursively(). If that isn't a problem, static is fine. I prefer not to limit potential recursions unnecessarily. Mark Brader "Male got pregnant -- on the first try." utzoo!sq!msb Newsweek article on high-tech conception msb@sq.com November 30, 1987
richardh@killer.UUCP (Richard Hargrove) (11/27/87)
In article <2218@killer.UUCP>, richardh@killer.UUCP (Richard Hargrove) writes: > In article <1987Nov22.085210.20641@sq.uucp>, msb@sq.uucp (Mark Brader) writes: > > There have been several followups regarding the code: > > (deleted) > > The above requests that a new variable "k" be created, and destroyed > > again, on each iteration of the loop. Since it is destroyed each time, > > No it doesn't! It requests that a variable "k" be allocated and be visible > > > > > But the value of "k" is NOT guaranteed to be retained from one iteration > > to the next, and you must not assume it will be. If you want that, you > > Yes it is! The variable's scope is the block in which it is defined. > Time for some humble pie along with all the other Thanksgiving deserts. I am obviously in error. If my claim above were true then objects declared local to the block would be visible to the loop control code, which they obviously aren't. Hope I don't need too much flame retardant. richard hargrove ...!killer!richardh ------------------- Found on a Post-It attached to the front of a terminal in a deserted office in downtown Wichita: "Aunty Em, Hate you. Hate Kansas. Took the dog. Dorothy" ---------------------------------------------
platt@emory.uucp (Dan Platt) (11/28/87)
===================================================================
Actually, it might be worthwhile to point out that in several compilers,
locally defined variables are placed on the stack as needed, and popped when
you've left the loop. Since there may be other stuff being put on the stack
and being popped in between your accesses once you've left the {} where
a variable was assigned, you can't assume the 'first use' in the {} will
be the same as the value it had the last time you were in the {}. This is
also how re-entrant and recursive code is handled: the arguments AND the
local variables are allocated space on the stack, so that when the routine
returns a value to the older version of itself, all its information is still
sitting there waiting for it on the stack.
Dan PlattI1090801%DBSTU1.BITNET@CUNYVM.CUNY.EDU (11/29/87)
I think there is a good reason for a C-compiler to allocate
space for all local variables at the beginning of a function.
Look at the following example:
int f()
{
if (...)
{ int a;
...
goto label2;
label1: ... /* do someting with a */
}
else
{ int b;
...
goto label1;
label2: ... /* do something with b */
}
}
In this case it is not possible to allocate the same space
for the variables a and b. If you allocate space for a at the
start of the then-block there is no space allocated for variable
b after you do the jump into the else-part (at least not until
the compiler does some very tricky code generation).
Another reason for allocating space at the beginning of
a function is the gain in code-space and runtime (but perhaps
with a loss of data-space, which may only become a problem in
recursive calls).
Ulf Gruene
I1090801@DBSTU1.BITNET
Technische Universitaet Braunschweig
West Germanywendt@arizona.edu (Alan Lee Wendt) (11/30/87)
Regarding whether k is allocated and deallocated on each iteration of the loop: > > for (;;) { > > int k; > > ... > > } As Richard H. states, the variable's scope is the block in which it is created. But this block does not include any expressions outside of the curly braces, hence does not include the for initialization, test and increment expression. Therefore control is exiting this block and re-entering, and the variable is being allocated and deallocated repeatedly, at least as far as the language semantics go. (A compiler may legally choose to re-use k's location while evaluating the for-expressions). To convince yourself that, the "block defined" can't possibly include the for-expressions, you can look at the definition of a block. Or, consider the situation of the poor compiler writer if someone actually mentioned the variable k inside one of the for-expressions. The compiler writer would be in a position of having to compile a reference to k before k has been declared. Alan W.
tainter@ihlpg.ATT.COM (Tainter) (11/30/87)
>But the value of "k" is NOT guaranteed to be retained from one iteration >to the next, and you must not assume it will be. If you want that, you >have to declare "k" in a larger scope including the for-header. And you can do this without getting k too far away, as so: { int k; /* a variable that lives for the life of this loop */ for (;;) { ... } } Why is this so unpopular? --j.a.tainter
woerz@iaoobelix.UUCP (12/01/87)
> /***** iaoobelix:comp.lang.c / brl-adm!I1090801%DBSTU1.BITNET@CU / 1:41 pm Nov 29, 1987*/ > I think there is a good reason for a C-compiler to allocate > space for all local variables at the beginning of a function. > Look at the following example: > int f() > { > if (...) > { int a; > ... > goto label2; > label1: ... /* do someting with a */ > } > else > { int b; > ... > goto label1; > label2: ... /* do something with b */ > } > } > In this case it is not possible to allocate the same space > for the variables a and b. If you allocate space for a at the > start of the then-block there is no space allocated for variable > b after you do the jump into the else-part (at least not until > the compiler does some very tricky code generation). I think that it is possible in this case, if you use a label the same way you use the normal entry to a block. That is you have to allocate space if you hit a label and there are local variables for that block. You will have to jump around the code, if you entered the block at another entry. I'm not saying that this is worth to do, but I think that it's doable without some tricky code generation. > ... > > Ulf Gruene > I1090801@DBSTU1.BITNET > Technische Universitaet Braunschweig > West Germany > /* ---------- */ ------------------------------------------------------------------------------ Dieter Woerz Fraunhofer Institut fuer Arbeitswirtschaft und Organisation Abt. 453 Holzgartenstrasse 17 D-7000 Stuttgart 1 W-Germany BITNET: iaoobel.uucp!woerz@unido.bitnet UUCP: ...{uunet!unido, pyramid}!iaoobel!woerz
cdwf@root.co.uk (Clive D.W. Feather) (12/01/87)
In article <10572@brl-adm.ARPA> I1090801%DBSTU1.BITNET@CUNYVM.CUNY.EDU writes: >I think there is a good reason for a C-compiler to allocate >space for all local variables at the beginning of a function. >Look at the following example: [Example involving jumping out of one block with 'a' declared, and into another block with 'b' declared] >In this case it is not possible to allocate the same space >for the variables a and b. If you allocate space for a at the >start of the then-block there is no space allocated for variable >b after you do the jump into the else-part (at least not until >the compiler does some very tricky code generation). On the contrary, a only exists in the then-block, and b in the else-block. When you jump out of a block, all variables declared in it cease to exist. When you jump into a block, all variables declared in it come into existence (though they may not have been initialised correctly). For example, the code: main () { /* Some code, #1 */ goto label; /* Some code, #2 */ { int x = 72; /* Some code, #3 */ label: /* Some code, #4 */ } } has the same semantics as: main () { int j_label; /* Some code, #1 */ { j_label = 1; goto label; } /* Some code, #2 */ j_label = 0; label: { int x; if (j_label) goto label_2; x = 72; /* Some code, #3 */ label_2: j_label = 0; /* In case we ever come back again */ /* Some code, #4 */ } } [Yes, I know this looks terrible. Serves you right for using goto.]