lins@apple.com (Chuck Lins) (04/30/91)
Execution units are the enforcement agents of the RISC revolution.
Does anyone know how nested procedures affect the ability to pass parameters
via registers? If there was no up-level access everything would work fine,
but with this facility you get all sorts of problems. Uplevel access would
also seem to affect dataflow analysis (the compiler could think that a
variable is 'dead' when in reality it's going to get accessed by a nested
local procedure.
Maybe all the potential hair is why Pascal and Modula-2 compiler writers
just pass all parameters via the stack.
Are there (nice) solutions to these problems. References welcome.
Thanks in advance from,
Chuck Lins
lins@apple.com
[Can one reference a named parameter in an enclosing procedure? If so, I
can imagine that would force them onto the stack. -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.zlsiial@cms.manchester-computing-centre.ac.uk (A. V. Le Blanc) (04/30/91)
The ETH Pascal 6000 compiler, at least the versions I used,
passed the first four arguments to procedures and functions
in registers. It was also possible to change this for
certain procedures or functions, either increasing or decreasing
the number of parameters passed.
A. V. Le Blanc
Computing Centre
University of Manchester
ZLSIIAL@uk.ac.mcc.cms
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.mike@yalla.tuwien.ac.at (Michael K. Gschwind) (04/30/91)
In article <1991Apr30.022048.4539@iecc.cambridge.ma.us> lins@apple.com (Chuck Lins) writes: >Does anyone know how nested procedures affect the ability to pass parameters >via registers? ... Well, there is an easy solution: just generate a list of all variables used by nested procedures - then you can store these (AND ONLY THESE, they are bound to be very few) in well-known stack locations. All other variables can be kept in registers and pronounced dead. In this set-up, a variable is dead, if *) it is dead in the procedure *) and +) either no nested procedures are called +) or the varaible is dead upon entry in this procedure There are two possibilities to act, if you know a parameter is going to be referenced in nested procedures. Either push it on the stack upon function entry or only if you're calling a nested procedure which uses it (You will need the transitive closure, I guess) - the latter mey be preferable in some circumstances, but the fromer is easier to implement: Just search the nested functions and check if the parameter is ever used. If so, reserve a stack slot and push immediately. PROCEDURE x( a, b, c ,d : integer) ; PROCEDURE y ( e,f,g : real); BEGIN write (a+f); END BEGIN if (d = 0) y(a,b,c); else write (a); END You either do: _x: /* a into well-know location, no need to save b,c,d */ st rA, fp+_a test rD jne @L1 <call y> return @L1: <write> return Or: _x: test rD jne @L1 /* a into well-know loc */ st rA, fp+_a <call y> return @L1: <write> return [Can one reference a named parameter in an enclosing procedure? If so, I can imagine that would force them onto the stack. -John] I dunno, but I guess so. Shouldn't be any complication in any case. Maybe somebody could check out the relevant facts? Register allocation across all nested functions is *) impossible in Pascal (since nested procedures may be transmitted via PROCEDURE parameters to non-related functions) and *) (I guess) not worthwhile in Modula-2 (where only top-level functions may be assigned to procedure-type variables - thus you can have a fall-back strategy for all top-level functions and thus restrict register allocation to a top-level function and all its nested functions) except if used with a global register allocation algorithm. BTW, does anybody know about compilers trying to find 'optimal' register assignment for top-level Modula-2 functions and all nested functions? Register allocation could probably done quite easily for such a block of related functions, as the only entry point from without this block is the top-level function. Thus the compiler knows all the places where the nested functions are called. Michael K. Gschwind, Dept. of VLSI-Design, Vienna University of Technology mike@vlsivie.tuwien.ac.at || mike@vlsivie.uucp Voice: (++43).1.58801 8144 || Fax: (++43).1.569697 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
mike@vlsivie.tuwien.ac.at (Michael K. Gschwind) (04/30/91)
In article <1991Apr30.022048.4539@iecc.cambridge.ma.us> lins@apple.com (Chuck Lins) writes: >Does anyone know how nested procedures affect the ability to pass parameters >via registers? ... Well, there is an easy solution: just generate a list of all variables used by nested procedures - then you can store these (AND ONLY THESE, they are bound to be very few) in well-known stack locations. All other variables can be kept in registers and pronounced dead. In this set-up, a variable is dead, if *) it is dead in the procedure *) and +) either no nested procedures are called +) or the varaible is dead upon entry in this procedure There are two possibilities to act, if you know a parameter is going to be referenced in nested procedures. Either push it on the stack upon function entry or only if you're calling a nested procedure which uses it (You will need the transitive closure, I guess) - the latter mey be preferable in some circumstances, but the fromer is easier to implement: Just search the nested functions and check if the parameter is ever used. If so, reserve a stack slot and push immediately. PROCEDURE x( a, b, c ,d : integer) ; PROCEDURE y ( e,f,g : real); BEGIN write (a+f); END BEGIN if (d = 0) y(a,b,c); else write (a); END You either do: _x: /* a into well-know location, no need to save b,c,d */ st rA, fp+_a test rD jne @L1 <call y> return @L1: <write> return Or: _x: test rD jne @L1 /* a into well-know loc */ st rA, fp+_a <call y> return @L1: <write> return [Can one reference a named parameter in an enclosing procedure? If so, I can imagine that would force them onto the stack. -John] I dunno, but I guess so. Shouldn't be any complication in any case. Maybe somebody could check out the relevant facts? Register allocation across all nested functions is *) impossible in Pascal (since nested procedures may be transmitted via PROCEDURE parameters to non-related functions) and *) (I guess) not worthwhile in Modula-2 (where only top-level functions may be assigned to procedure-type variables - thus you can have a fall-back strategy for all top-level functions and thus restrict register allocation to a top-level function and all its nested functions) except if used with a global register allocation algorithm. BTW, does anybody know about compilers trying to find 'optimal' register assignment for top-level Modula-2 functions and all nested functions? Register allocation could probably done quite easily for such a block of related functions, as the only entry point from without this block is the top-level function. Thus the compiler knows all the places where the nested functions are called. Michael K. Gschwind, Dept. of VLSI-Design, Vienna University of Technology mike@vlsivie.tuwien.ac.at || mike@vlsivie.uucp Voice: (++43).1.58801 8144 || Fax: (++43).1.569697 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
preston@ariel.rice.edu (Preston Briggs) (04/30/91)
Chuck Lins <lins@apple.com> writes: >Does anyone know how nested procedures affect the ability to pass parameters >via registers? If there was no up-level access everything would work fine, >but with this facility you get all sorts of problems. Uplevel access would >also seem to affect dataflow analysis (the compiler could think that a >variable is 'dead' when in reality it's going to get accessed by a nested >local procedure. One approach would be to pass the first few parameters in registers. However, in the called routine, it may be necessary to store the parameters on the stack, in standard locations. Imagine we have 3 procedures: A, B, and C, where C is nested inside B. When A calls B, it can pass (say) the first 4 suitable arguments in registers (where suitable means not a record or array). When C is compiled (it's compiled before B, since it's nested), we record which of B's parameters and variables are referenced. For each uplevel reference, we assume that the values are in some standard place on the stack. When compiling B, we must leave space on the stack for all the parameters. When we see a call to C, we know which variables and parameters might be accessed in C, and must emit code to store any "enregistered" variables into their home locations on the stack. Note that we must also recognize the effects of any procedures nested within C. The above version is "flow-insensitive" analysis, in that we assume that any reference can be reached and we don't bother about noticing whether DEFs come before USEs. It sounds slightly hairy, but really it's just setting a couple of flags per variable in the symbol table, and then following conventions while generating code. A more precise version would be "flow-sensitive". Here we do a little more work to recognize that a variable is always DEF'd before USE, and is therefore dead. This is all pretty informal and will take some effort to fill out the details. We're (probably) saved from the effort of complete call graph construction and interprocedural analysis by the fact that we're considering only lexically scoped procedures, without first-class procedures. Preston Briggs -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
mike@taumet.com (Michael S. Ball) (04/30/91)
In article <1991Apr30.022048.4539@iecc.cambridge.ma.us> Chuck Lins <lins@apple.com> writes: >Does anyone know how nested procedures affect the ability to pass parameters >via registers? If there was no up-level access everything would work fine, >but with this facility you get all sorts of problems. Uplevel access would >also seem to affect dataflow analysis (the compiler could think that a >variable is 'dead' when in reality it's going to get accessed by a nested >local procedure. Actually, since you have the bodies of the nested procedures available before compiling the body of the enclosing procedure you have all of the data necessary to do a good job. Any register parameter which is used by uplevel reference is simply stored on the stack, just as it would be in a C function using varargs. I don't know that Pascal and Modula compilers pass parameters on the stack any more than C compilers do. My experience is that they use the calling sequence established by the execution environment. Of course with languages like Pascal which encourage internal linkage, compilers are able to establish their own sequences, and on machines like the VAX, where calls are expensive, they frequently do. You can do the same with C, but static functions seem to be rare. -- Michael S. Ball mike@taumet.com TauMetric Corporation (619)697-7607 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
ram+@cs.cmu.edu (Rob MacLachlan) (05/01/91)
>Does anyone know how nested procedures affect the ability to pass parameters >via registers? If there was no up-level access everything would work fine, >but with this facility you get all sorts of problems. In "mostly functional" langauges like Lisp and ML, the compiler usually only forces out to memory variables that may be side-effected. Variables that are initialized once and then never reassigned don't cause any problems, since the value can be freely copied. >Uplevel access would also seem to affect dataflow analysis (the compiler >could think that a variable is 'dead' when in reality it's going to get >accessed by a nested local procedure. A common approach is to find all variables that may be accessed uplevel by a particular function, and then pass those values as additional implicit arguments. This causes the uplevel copy of the variable to be live until you are done with it. Robert MacLachlan (ram+@cs.cmu.edu) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
mauney@eos.ncsu.edu (Dr. Jon Mauney) (05/02/91)
Most of the discussion has mentioned ways of forcing parameters passed in
registers onto the stack for non-local reference. Note that it is not
strictly necessary for such parameters to be on the stack. Since the
references occur within internal functions, code could be compiled to use
the value in the register. You would have to change the calling sequence
so as to preserve the register, but you have control of both sides of the
call, so that is possible. Conceivably, this could be done even if the
procedure is passed as a parameter -- just make sure the register value is
part of the closure that you pass.
I'm not claiming it's worth the trouble...
--
Jon Mauney, parsing partisan
Computer Science Dept.
N.C. State University
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.mario@cs.man.ac.uk (Mario Wolczko) (05/02/91)
In article <1991Apr30.022048.4539@iecc.cambridge.ma.us>, lins@apple.com (Chuck Lins) writes: > Does anyone know how nested procedures affect the ability to pass parameters > via registers? ... This is a particularly gruesome problem in languages that have procedures whose closures are first-class objects, and can outlive their surrounding context. Smalltalk and Scheme are examples. In Smalltalk, for example, you can write: method: arg ... var := [ :x | x + arg]. ^var This returns a "block" (the expression in brackets; similar to a bound lambda-expression in Scheme) that references the argument in its enclosing method, despite the block outliving the method invocation. My Scheme is a little rusty, but I think it would be something like: (define method (arg) (lambda (x) (+ x arg))) The problem here is that the closure for the block/function needs to reference the activation record for "method", even when control has returned from "method". A naive implementation of this is to put every activation in the heap, and garbage collect dead ones [GR83]. Better is to put activation records on the stack, and defer conversion to heap form until absolutely necessary [DS84]. This gets trickier when your activations live in register windows [Ung87], which is where your question comes in. In the Smalltalk compiler I'm working on at the moment, one phase of the compiler attempts to locate variables which are genuinely shared between activations (including dataflow and liveness analysis), and then allocates a value holder for them in the heap. Otherwise they're truly local and can go in registers. I can supply more details if you're interested. It should be a lot simpler in languages with strict LIFO activations. Mario Wolczko [GR83] A. Goldberg, D. Robson, "Smalltalk-80: The Language and its Implementation," Addison-Wesley, 1983. [DS84] L. P. Deutsch, A. M. Schiffman, Efficient Implementation of the Smalltalk-80 System, ACM POPL11, 1984. [Ung87] D. M. Ungar, The Design and Evaluation of a High Performance Smalltalk System, MIT Press, 1987. Dept. of Computer Science Internet: mario@cs.man.ac.uk The University uucp: mcsun!ukc!man.cs!mario Manchester M13 9PL JANET: mario@uk.ac.man.cs U.K. Tel: +44-61-275 6146 (FAX: 6236) -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
mike@vlsivie.tuwien.ac.at (Michael K. Gschwind) (05/04/91)
Dr. Jon Mauney writes: >Most of the discussion has mentioned ways of forcing parameters passed in >registers onto the stack for non-local reference. Note that it is not >strictly necessary for such parameters to be on the stack. Since the >references occur within internal functions, code could be compiled to use >the value in the register. You would have to change the calling sequence >so as to preserve the register, but you have control of both sides of the >call, so that is possible. Conceivably, this could be done even if the >procedure is passed as a parameter -- just make sure the register value is >part of the closure that you pass. > >I'm not claiming it's worth the trouble... It IS worth the trouble if you're doing global register allocation or at least register allocation relative to a top-level function and its nested procedures. IT IS (probably) NOT worth it if you're only trying to prevent forcing parameters on the stack because they are used in some nested procedures. You might of course find a simple algorithm which would not cost much, but to be really effective, you'd probably have to do extensive data flow analysis. Parameters used in nested procedures are (probably) too rare warrant such extensive data flow analysis. But if you're doing data flow analysis anyway, you'll probably get it for free. You can then probably apply the strategy adopted for local variables used in nested functions to parameters as well (or vice versa ;-). You write that "this could be done even if the procedure is passed as a parameter". This is not correct in the general case, and the case you line out, namely "just make sure the register value is part of the closure that you pass", is not feasable. Procedures passed as parameters can be called from just about any context, e.g., library functions, separately compiled modules etc., thus you cannot change the calling sequence. In the case of functions passed as parameters/procedure typed variables, you always have to have a standardized calling sequence. You could of course always store the calling conventions of every function in a library or external module in a data base, but what do you do if you are PascalWorkstations, Inc. and your shared library has a bug? You have to keep the same calling conventions for a function 'x' once you have sold a single copy of a shared library containing it, or all programs linked with the new, improved shared library, but compiled with the old one (i.e., all commercial programs sold for your workstation) will no longer work! Modula-2 is much easier here: if you want to do aggressive register allocation, you can optimize all top-level functions + their nested functions, while retaining a consistent calling convention for top-level functions, which are the only functions which may be assigned to procedure-typed variables. bye, mike Michael K. Gschwind, Dept. of VLSI-Design, Vienna University of Technology mike@vlsivie.tuwien.ac.at || mike@vlsivie.uucp Voice: (++43).1.58801 8144 || Fax: (++43).1.569697 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.
mauney@eos.ncsu.edu (Dr. Jon Mauney) (05/07/91)
I wrote >> ... Conceivably, this could be done even if the >>procedure is passed as a parameter -- just make sure the register value is >>part of the closure that you pass. >> >>I'm not claiming it's worth the trouble... Michael Gschwind replies >You write that "this could be done even if the procedure is passed as a >parameter". This is not correct in the general case, and the case you line >out, namely "just make sure the register value is part of the closure that >you pass", is not feasable. Procedures passed as parameters can be called >from just about any context, e.g., library functions, separately compiled >modules etc., thus you cannot change the calling sequence. In the case of >functions passed as parameters/procedure typed variables, you always have >to have a standardized calling sequence. The discussion is worth continuing only in that it illustrates a very important principle of compiler implementation: you can make things work just about any way you want as long as you are pigheaded enough to keep at it. "In the world of mules, there are no rules" -- Ogden Nash In this case, the function passed as a parameter will have to help set up its own environment. Essentially you would construct a thunk that sets up the environment and then calls the funciton; the thunk would then get passed instead of the original. You probably have to do this sort of thing anyway, if you are passing Pascal procedures to library functions, since the library is probably going to assume a C style pointer to function, with no environment of any sort. (ah, but where does the thunk get the environment data in this case? Left as an exercise to the reader) Like I said, I continue the discussion not because I think anyone cares about leaving values in registers for use by nested procedures that are passed as callback functions to Xt library routines, but because one often hears the statement "it is impossible for a compiler to accomplish X, or to use technique Y for language Z." Usually such statements are not true. One simply has to think a little harder, change some other assumptions, and sometimes build a huge cumbersome mechanism to do it. And then decide whether it is worth it. -- Jon Mauney, parsing partisan Computer Science Dept. N.C. State University -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.