Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!rice!news From: preston@ariel.rice.edu (Preston Briggs) Newsgroups: comp.arch Subject: Re: more registers for ix86, was: Let's pretend Message-ID: <1991Jan8.225621.28731@rice.edu> Date: 8 Jan 91 22:56:21 GMT References: <1991Jan6.014925.10935@zoo.toronto.edu> Sender: news@rice.edu (News) Organization: Rice University, Houston Lines: 41 pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: >I'd like to repeat my usual fundamental truth on this: ... >[1] Examples: > >a+b+c+d this, on a single threaded CPU, only needs one register > to be compiled without spills. > >a/b + c*d this instead needs two registers for compiling without > spilling, because two things are going on at the same > time (logically). > >[2] Most expressions, staticall, are of the form 'a = b OP c' or >simpler; dynamically things cna be slightly more complicated. Note that >the operands may involve address computations. These examples gloss over the number of registers required for addressing and the amount of reuse available due to addressing. We all know about array addressing expressions. Consider also pointer chasing in C or Pascal and the addressing of non-local (and non-global) variables in Algol and descendants. A large portion of the work done by various forms of strength reduction, common subexpression elimination (local and global), and loop invariant code motion involve all these implied calculations and memory accesses. In the case of Fortran, very little of the user's explicit code is ever touched by the optimizer (mostly because it _is_ very simple, as mentioned above and in Knuth's "An emperical study of fortran..." paper). >[5] The reason is that most expressions are indeed stack based, i.e. the >lifetimes of spills nest nicely, while register machines assume the >worst case, i.e. all spills have completely unrelated lifetimes and have >to be managed explicitly. A multiple stack machine is a nice compromise. Are there any papers describing how to generate code for such a machine? It seems as though the many stacks must still be managed explicitely. Additionally, we must solve the problem of "which items on which stack" and "when do we pop what values from the stack". Preston Briggs