Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: Walter Banks Newsgroups: comp.lang.forth Subject: Re: Metrics on stack usage Date: Mon, 22 Sep 2014 13:58:07 -0400 Organization: Aioe.org NNTP Server Lines: 114 Message-ID: <5420632F.A458FAA@bytecraft.com> References: <541855C0.2558D27D@bytecraft.com> <7xmw9zletd.fsf@ruckus.brouhaha.com> <541891FE.9157C03@bytecraft.com> <2014Sep17.092044@mips.complang.tuwien.ac.at> <5419F72B.F5EC2F16@bytecraft.com> <2014Sep18.134054@mips.complang.tuwien.ac.at> <54203843.BD257924@bytecraft.com> <2014Sep22.171327@mips.complang.tuwien.ac.at> NNTP-Posting-Host: WS9whZ/ot+e+Q+IoL9T/mw.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org X-Mailer: Mozilla 4.79 [en]C-CCK-MCD NSCPCD479 (Windows NT 5.0; U) X-Accept-Language: en X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.forth:33513 Anton Ertl wrote: > Walter Banks writes: > >Anton Ertl wrote: > >> Can stack allocation across basic blocks be done? Sure, but can we do > >> it well? I don't see a heuristic for choosing which variables to keep > >> on the stack where spring out at me. If viewed like register > >> allocation, this is like a very small register set with irregular > >> access rules; the usual register sets are not very good at this kind > >> of thing, despite decades of research and development; that's why > >> architectures intended to be used with compilers have settled for > >> larger, regular ("general-purpose") register sets. > > > >Many of the ISA designs have larger general purpose register sets > >so that they can use open source public domain compiler tools most > >of which are using old compiler technology. Non orthogonal and > >special purpose register sets can be supported with current compiler > >technology especially those using strategy passes that process the full > >application data and control structure to plan out the actual code > >implementation. > > Are there any papers on that? It is pretty common approach in some of the embedded systems compilers especially for no orthogonal instruction sets. I don't know of any publication links.. It has shown up on some of the news groups from time to time in discussion. > > In any case, I doubt that, say, Intel or IBM are designing their > architectures for "open source public domain compiler tools most of > which are using old compiler technology". They have their own > compiler teams. Both IBM and Intel use GCC GNU or llvm. They have their own very capable compiler teams. There has been some instruction set innovation but still very mainstream . Some of the automotive and aerospace processors are very much non orthogonal. Automotive engine controllers eTPU families for example) have very different instruction sets. > >> * Forth programmers use a wide variety of techniques for dealing with > >> the limitations of stack-based programming, often very specific to > >> the program at hand, and exploiting knowledge that the Algol > >> compiler does not have (because it's not expressed in the Algol > >> source code). > > > >Do you have an example of the kind information that would be useful? > > Nothing from a real program at the moment, but information about > aliases or "don't care" behaviour is something that a compiler often > cannot know, and that could be helpful in reducing the stack load > (e.g., by moving memory accesses around). > > >> * Studies of Forth programs have found fewer dynamic conditional > >> branches and far more calls and returns than instruction statistics > >> for e.g., C-compiler generated programs. E.g., compare the date from > >> with > > > >> > > >> f%20x86%20Instruction%20Set%20Usage%20for%20DOS%20Windows%20 > > > >> Applications%20and%20Its%20Implication%20on%20Superscalar%20Design.pdf > > > >What is the underlying reason for lower dynamic conditionals. Is it the > >higher overall cost for using them encouraging the use of branchless > >code? > > One reason is probably that in Forth branchy code requires even more > mental effort than in other languages, because you have to keep track > of the stack depth and stack item arrangement, and make sure they > agree on control flow joins. Therefore Forth programmers tend to > avoid branching when they can. > > By contrast, C programs introduce additional branches with > short-circuit evaluation. > > >Do you know of any papers on code reliability in Forth applications given > >that functions don't have a formal interface? (The implication is the series > >terms in the system reliably are larger than say algol languages) > > You lost me in the last sentence. If you take normal reliability math and apply it to code and make some assumption about instruction reliability and then analyse the code you will result in a dimensionless number that can be used to compare two implementations and it will reliably (pun:) identify which implementation is more reliable. My experience doing this has been that the results are consistent independent which assumption is made about instruction reliability. The three most common assumptions we have made has been each instruction has a reliability of 1, reliability is equal to 1/cycles or 1/instruction_size. Parallel terms occur when there are independent paths that contribute to the overall result. Series terms are broken by a clean clear entrance and exit interface where one block may be replaced with a block having the same interface and the results are unchanged. What I was referring to was the lack of the component interface and that generally increases the probability of failure. The result is a dimensionless number but it can be computed automatically. (We have done it from machine code so that even the code generated tools do not need to be changed.) The data structure of an application is similar to McCabe's Cyclomatic Complexity. w..