1Prof. Bodik CS 164 Fall 2004 1Run-time organizationLecture 12Prof. Bodik CS 164 Fall 2004 2Status• We have covered the front-end phases– Lexical analysis–Parsing– Semantic analysis• Next are the back-end phases– Optimization– Code generation• We’ll do code generation first . . .Prof. Bodik CS 164 Fall 2004 3Run-time environments• Before discussing code generation, we need to understand what we are trying to generate• There are a number of standard techniques for structuring executable code that are widely usedProf. Bodik CS 164 Fall 2004 4Outline• Management of run-time resources• Correspondence between static (compile-time) and dynamic (run-time) structures• Storage organizationProf. Bodik CS 164 Fall 2004 5Run-time Resources• Execution of a program is initially under the control of the operating system• When a program is invoked:– The OS allocates space for the program– The code is loaded into part of the space– The OS jumps to the entry point (i.e., “main”)Prof. Bodik CS 164 Fall 2004 6Memory LayoutLow AddressHigh AddressMemoryCodeOther Space2Prof. Bodik CS 164 Fall 2004 7Notes• By tradition, pictures of machine organization have:– Low address at the top– High address at the bottom– Lines delimiting areas for different kinds of data• These pictures are simplifications– E.g., not all memory need be contiguousProf. Bodik CS 164 Fall 2004 8What is Other Space?• Holds all data for the program• Other Space = Data Space• Compiler is responsible for:– Generating code– Orchestrating use of the data areaProf. Bodik CS 164 Fall 2004 9Code Generation Goals•Two goals:– Correctness–Speed• Most complications in code generation come from trying to be fast as well as correctProf. Bodik CS 164 Fall 2004 10Assumptions about Execution1. Execution is sequential; control moves from one point in a program to another in a well-defined order2. When a procedure is called, control eventually returns to the point immediately after the callDo these assumptions always hold?Prof. Bodik CS 164 Fall 2004 11Activations• An invocation of procedure P is an activation of P•The lifetimeof an activation of P is– All the steps to execute P– Including all the steps in procedures P callsProf. Bodik CS 164 Fall 2004 12Lifetimes of Variables•The lifetime of a variable x is the portion of execution in which x is defined•Note that– Lifetime is a dynamic (run-time) concept– Scope is a static concept3Prof. Bodik CS 164 Fall 2004 13Activation Trees• Assumption (2) requires that when P calls Q, then Q returns before P does• Lifetimes of procedure activations are properly nested• Activation lifetimes can be depicted as a treeProf. Bodik CS 164 Fall 2004 14Exampleclass Main {int g() { return 1; }int f() {return g(); }void main() { g(); f(); }}MainfggProf. Bodik CS 164 Fall 2004 15Example 2class Main {int g() { return 1; }int f(int x) { if (x == 0) { return g(); }else { return f(x - 1); } }void main() { f(3); }}What is the activation tree for this example?Prof. Bodik CS 164 Fall 2004 16Notes• The activation tree depends on run-time behavior• The activation tree may be different for every program input• Since activations are properly nested, a stack can track currently active proceduresProf. Bodik CS 164 Fall 2004 17Exampleclass Main {int g() { return 1; }int f() { return g(); }void main() {g(); f(); }}Main StackMainProf. Bodik CS 164 Fall 2004 18ExampleMaingStackMaingclass Main {int g() {return 1; }int f() { return g(); }void main() { g(); f(); }}4Prof. Bodik CS 164 Fall 2004 19ExampleMaingfStackMainfclass Main {int g() { return 1; }int f() {return g(); }void main() { g(); f(); }}Prof. Bodik CS 164 Fall 2004 20ExampleMainfggStackMainfgclass Main {int g() { return 1;}int f() { return g(); }void main() { g(); f(); }}Prof. Bodik CS 164 Fall 2004 21Revised Memory LayoutLow AddressHigh AddressMemoryCodeStackProf. Bodik CS 164 Fall 2004 22Activation Records• The information needed to manage one procedure activation is called an activation record (AR) or frame• If procedure F calls G, then G’s activation record contains a mix of info about F and G.Prof. Bodik CS 164 Fall 2004 23What is in G’s AR when F calls G?•Fis “suspended” until G completes, at which point F resumes. G’s AR contains information needed to resume execution of F.•G’s AR may also contain:– G’s return value (needed by F)– Actual parameters to G (supplied by F)– Space for G’s local variablesProf. Bodik CS 164 Fall 2004 24The Contents of a Typical AR for G• Space for G’s return value• Actual parameters• Pointer to the previous activation record–The control link; points to AR of caller of G• Machine status prior to calling G– Contents of registers & program counter– Local variables• Other temporary values5Prof. Bodik CS 164 Fall 2004 25Example 2, Revisitedclass Main {int g() { return 1; }int f(int x) { if (x == 0) { return g(); }else { return f(x - 1); (**)} }void main() { f(3); (*)}} AR for f:return addresscontrol linkargumentresultProf. Bodik CS 164 Fall 2004 26Stack After Two Calls to fMain(**)2(result)f(*)3(result)fProf. Bodik CS 164 Fall 2004 27Notes•Mainhas no argument or local variables and its result is never used; its AR is uninteresting•(*) and (**) are return addresses of the invocations of f– The return address is where execution resumes after a procedure call finishes• This is only one of many possible AR designs– Would also work for C, Pascal, FORTRAN, etc.Prof. Bodik CS 164 Fall 2004 28The Main PointThe compiler must determine, at compile-time, the layout of activation records and generate code that correctly accesses locations in the activation recordThus, the AR layout and the code generator must be designed together!Prof. Bodik CS 164 Fall 2004 29ExampleThe picture shows the state after the call to 2nd invocation of f returnsMain(**)21f(*)3(result)fProf. Bodik CS 164 Fall 2004 30Discussion• The advantage of placing the return value 1st in a frame is that the caller can find it at a fixed offset from its own frame• There is nothing magic about this organization– Can rearrange order of frame elements– Can divide caller/callee responsibilities differently– An organization is better if it improves execution speed or simplifies code generation6Prof. Bodik CS 164 Fall 2004 31Discussion (Cont.)• Real compilers hold as much of
View Full Document
Unlocking...