Xref: utzoo comp.arch:19641 alt.folklore.computers:7702 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!ira.uka.de!sun.rhrk.uni-kl.de!uklirb!kirchner From: kirchner@informatik.uni-kl.de (Reinhard Kirchner) Newsgroups: comp.arch,alt.folklore.computers Subject: Why my stack grew up and this was wrong Keywords: stack Message-ID: <7298@uklirb.informatik.uni-kl.de> Date: 5 Dec 90 11:53:27 GMT Sender: news@uklirb.informatik.uni-kl.de Lines: 82 There was a discussion in at.folklore.computers about why stacks are growing downwards, not up as would seem natural. Since this is clearly an architectural issue I am posting my experiences about this to comp.arch as well as alt.folklore.computers. From the operating system point of view the stack my grow in either direction, there is no preference ( I think ). Detection of overflow my be simpler in one direction, but thats all. Stack and heap should always grow in opposite directions, so you can allocate one pool of memory for both without any fixed size for one. Now the architectural ( instruction set / registers ) problems: I run into them when I designed a virtual machine for pascal with numeric extensions ( the famous Pascal-SC, now even more extended and called Pascal-XSC ) about 13 years ago .... The name of this architecture was ( and is ) KL/P, since we are here in KaisersLautern, and it was for Pascal, and every real computer has a '/' ... How are the choices: a. Stack growing upward a1 -Stackpointer pointing to the first free byte a2 -SP pointing to the last byte a3 -SP pointing to the TOP-object and keeping its length somewhere in a special register b. Stack growing downward b1 -SP pointing to the last byte which is also adress of Top-object b2 -SP pointing to first free byte Now we not only have to handle the stack, but also to adress items in it, like parameters, locals, function results etc. Therefore we need some base-addresses, one per lexical level, which may reside in baseregisters or in linked stackframes. Anyway, if this base-point is between params and locals we need +/- adresses, otherwise only one direction. If we use baseregisters we need these also for adressing elements of records ( structures ), and since these are referenced by there first byte the offset in this case must be positive. Looking at the stack alone gives a clear preference of b1 since top is a very often needed address. In all other cases we have to compute addresses to access top. No using a base address to some point makes it difficult: When designing KL/P I had to find a compact encoding for small offsets, so I could not deal with a sign bit. This forced me to positive offsets. With a b1-stack I had to address over all locals to find parameters and function results. Now in a numerical environment locals, parameters and even function-results are often quite large vectors or matrices. So I decided to use a a1-stack. Our first interpreter was on a Z80, the handling was tricky anyway and I did not want to use the z80-Stack because this was needed for the interpretation, and having z80-data and kl/p-data mixed seemed a reliability issue.... From today and much more experience I must say: I should have used the z80-stack ( b1 ), and should looked for a solution to the positive-offset-problem, perhaps by additional address-modes etc. Using the z80-stack would have given a lot of performance, this would have outweighted the trouble. So far the story of my stack R. Kirchner Univ. Kaiserslautern Germany Computer Science kirchner@uklirb.informatik.uni-kl.de kinf89@dkluni01.bitnet Brought to you by Super Global Mega Corp .com